いまさらながら，素数判定 @ Haskell

とりあえず，試し割りと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 ((0/=).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 = (0, 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乱択アルゴリズムになっていないというオチ．
ランダムに選んでチェックではなく，素数を前から順に何個かチェックになっている．