Blanktar

  1. top
  2. blog
  3. 2015
  4. 03

Haskellでエラトステネスの篩

Haskellで素数のリストを作ってみた。

dropMultiples :: Integral a => a -> [a] -> [a]
--dropMultiples x ys = filter (\z -> 0 /= (mod z x)) ys
dropMultiples x = filter ((0 /=) . (`mod` x))  -- ポイントフリーにしてみたけど微妙?

takePrimes :: Integral a => [a] -> [a]
takePrimes []     = []
takePrimes (x:xs) = x : (takePrimes $ dropMultiples x xs)

primes :: Integral a => [a]
primes = takePrimes [2..]

main :: IO ()
main = print $ take 10 primes

エラトステネスの篩をかなり安直に書いただけ。 とりあえず10個目まで出力。

こんな愚直な実装でも無限に計算できる訳で、遅延評価ってのは凄いねぇ。