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

Haskellでエラトステネスの篩

2015-03-24

• 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個目まで出力。

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