とりあえず，試し割りとMiller-Rabin．

Miller-Rabinはアルゴリズム自体は簡単．

なんで，こんなコードがほぼ正しい答えを返すか若干不思議である

（乱択アルゴリズムは，相当単純なのに，まぁまぁなものが多い）．

```module IsPrime where
import Control.Arrow (first)
import Modulo (powMod)
-- ============================================================
-- Primality test by trial division
-- ============================================================
primes :: Integral a => [a]
primes = 2:filter isPrimeDivision [3,5..]
isPrimeDivision :: Integral a => a -> Bool
isPrimeDivision 1 = False
isPrimeDivision n = all ((/=).mod n).takeWhile (<=u) \$ primes
where u = floor.sqrt.fromIntegral \$ n
-- ============================================================
-- Primality test by Miller-Rabin
-- ============================================================
-- if a = 2^r * d then return (r, d)
index2 :: (Integral a, Enum b, Num b) => a -> (b, a)
index2 a | even a    = first succ.index2.div a \$ 2
| otherwise = (, a)
-- True  : n is probably prime
-- False : n is composite
millerRabinPrimality :: (Integral a, Integral b) => a -> Int -> b -> a -> Bool
millerRabinPrimality n s d a
| powMod a d n == 1 = True
| otherwise         = any (== n - 1).take s.iterate ((`mod` n).(^2)).powMod a d \$ n
isPrimeMillerRabin :: (Integral a) => a -> Int -> Bool
isPrimeMillerRabin n k
| n == 1    = False
| n == 2    = True
| even n    = False
| otherwise = all (millerRabinPrimality n s d).take k.takeWhile (< n) \$ primes
where (s,d) = index2 \$ n - 1
```

コードをよーく見ると分かるが，このMiller-Rabin乱択アルゴリズムになっていないというオチ．

ランダムに選んでチェックではなく，素数を前から順に何個かチェックになっている．