## 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```