In today’s Programming Praxis exercise we have to implement an algorithm to prove the primality of a number. Let’s get started, shall we?
import Data.Bits import Data.List
the tdFactors and expm functions have both been featured in previous exercises.
tdFactors :: Integer -> [Integer] tdFactors n = f n [2..floor . sqrt $ fromIntegral n] where f _  =  f r (x:xs) | mod r x == 0 = x : f (div r x) (x:xs) | otherwise = f r xs expm :: Integer -> Integer -> Integer -> Integer expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 . filter (flip testBit 0 . snd) . zip (iterate (flip mod m . (^ 2)) b) . takeWhile (> 0) $ iterate (`shiftR` 1) e
Unfortunately, these math-heavy problems typically resist shortening, so this is pretty similar to the Scheme solution.
isPrime :: Integer -> Bool isPrime n = f 2 $ tdFactors (n - 1) where f _  = False f b (q:qs) | expm b (n - 1) n /= 1 = f (b + 1) (q:qs) | expm b (n - 1 `div` q) n /= 1 = True | otherwise = f b qs
All that’s left is a quick test:
main :: IO () main = print . isPrime $ 2^89 - 1