Miller–Rabin primality test: Difference between revisions

Content added Content deleted
(→‎{{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 `elem` primesTo100 = return True
isMillerRabinPrime n | even n = return (2 == n)
| n `elem` primesTo100 = return True
| otherwise = do
| 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
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"