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

### Like this:

Like Loading...

*Related*

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

This entry was posted on February 2, 2010 at 10:18 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply