Miller–Rabin primality test: Difference between revisions

Content added Content deleted
Line 1,212: Line 1,212:
primesTo100 :: [Integer]
primesTo100 :: [Integer]
primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primesTo100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]



-- powerMod m x n = x^n `mod` m
-- powerMod m x n = x^n `mod` m
Line 1,221: Line 1,220:
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y
| otherwise = f (i-1) b (b*y `rem` m)
| otherwise = f (i-1) b (b*y `rem` m)
⚫
</lang>


{{out|Sample output}}

⚫
<pre>Testing in GHCi:
--------------------------------------

⚫
Testing in GHCi:
~> isPrime 4547337172376300111955330758342147474062293202868155909489
~> isPrime 4547337172376300111955330758342147474062293202868155909489
True
True
Line 1,233: Line 1,231:


*~> dropWhile (<900) $ filter isPrime [2..1000]
*~> dropWhile (<900) $ filter isPrime [2..1000]
[907,911,919,929,937,941,947,953,967,971,977,983,991,997]
[907,911,919,929,937,941,947,953,967,971,977,983,991,997]</pre>
⚫
</lang>


=={{header|J}}==
=={{header|J}}==
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"