Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→Python: Proved correct up to large N: Extra tests) |
(→{{header|Haskell}}: corrected code) |
||
Line 1,090: | Line 1,090: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
{{incorrect|Haskell|946 is not prime?}} |
|||
{{works with|Haskell|6.10.4}} |
{{works with|Haskell|6.10.4}} |
||
* Ideas taken from [http://primes.utm.edu/prove/prove2_3.html Primality proving] |
* Ideas taken from [http://primes.utm.edu/prove/prove2_3.html Primality proving] |
||
Line 1,121: | Line 1,120: | ||
isMillerRabinPrime :: Integer -> IO Bool |
isMillerRabinPrime :: Integer -> IO Bool |
||
isMillerRabinPrime n | n |
isMillerRabinPrime n | even n = return (2 == n) |
||
| n `elem` primesTo100 = return True |
|||
| otherwise = do |
|||
let pn = pred n |
let pn = pred n |
||
e = uncurry (++) . second(take 1) . span even . iterate (`div` 2) $ pn |
e = uncurry (++) . second(take 1) . span even . iterate (`div` 2) $ pn |