Haskellのお勉強 その１６

エラトステネスの篩(ふるい)をHaskellで書く

エラトステネスの篩とは、与えられた整数以下の素数すべてを探し出す素数判定アルゴリズムの一種で、
古代ギリシャの学者であるエラトステネスによって紀元前3世紀頃に考案された。

このアルゴリズムでは、任意の数までの素数を求める場合、
まず2から任意の数までの整数のリストを用意し、そのリストの中から最初の素数である2の倍数を消していく。
リストに残った整数のうち、先頭にある3が次の素数である。
次に、リストの中からその先頭にある素数である3の倍数を消してゆき、
残った整数のうち先頭にある5が次の素数である。このように、先頭に残った数の倍数をリストから消してゆき、
その都度先頭に残った数を集めていくと、結果的に素数のリストを得られるというカラクリ。

以下、素数を小さい方から１００個求めるプログラム

import System
main = print $ take 100 primenumber 

{-エラトステネスの篩-}
sieveOfEratosthenes :: [Int] -> [Int]
sieveOfEratosthenes (x:xs) = x: sieveOfEratosthenes [y|y<-xs, mod y x /=0]  

{-無限素数リスト-}
primenumber :: [Int]
primenumber = sieveOfEratosthenes [2..]

ちなみに、sieveOfEratosthenes関数に渡されるリストの先頭は素数になる。
なぜなら、渡されたリストの中から、その素数で割り切れる数を省く以下の内包表記があるから。

[y|y<-xs, mod y x /=0]

んー、sieveOfEratosthenes関数は見事にエラトステネスの篩になっとるな。
これが関数型言語のすげーところか。