Programming Praxis - Proving Primality

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?

Some imports:

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

About these ads

Tags: bonsai, code, Haskell, kata, praxis, primality, prime, programming, proving