HaHaHa!(old)

■ 誇大宣伝ではないエラトステネスの篩

無限リストの虚仮威し(オッ．)の例としてよくあるのがエラトステネスの篩と

称されている

 primes = [ p | (p:_) <- iterate sieve [2..] ]
 sieve (p:ps) = [ x | x <- ps, mod x p /= 0 ]

とか

 primes = sieve [2..]
 sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]

というプログラム．でも

遅延評価によるエラトステネスの篩にも書かれているように「等差数列で倍数が取り除けるということを使って初めて篩と呼べるので、これをエラトステネスの篩と呼ぶのは実は誇大宣伝だ。」

そこで，誇大宣伝ではないエラトステネスの篩の実装をば．．．

 type Table = ([Int],[Int],[Int]) -- (新規の素数リスト，篩に使う素数列，被篩数列)
 fst3 (x,_,_) = x

 primes :: [Int]
 primes = concatMap fst3 $ iterate sieve ([2],[2],[2..])
 sieve :: Table -> Table
 sieve (ps,q:qs,ss)
  = let (xs,ys) = span (q*q >) ss
    in (xs,qs++xs,filter ((/= 0) . (`mod` q)) ys)

(tさんのコメントを受けて，コードを修正しました: 2006/06/19)

これは 1000000個の素数 - HaHaHa!(old) - haskellの

高速版より性能がよいはず．

10,000,000番目の素数は 179,424,671 (179,424,691は10000001番目の素数で

した 2006/06/19)．primes !! 9999999 を計算するまでに掛った時間は

CPU: Intel(R) Pentium(R) M processor 2.13GHz 
OS : Ubuntu Linux 6.06
GHC option : -O 

で，

1561.57s user 3.05s system 95% cpu 27:13.98 total

という結果でした．