HaHaHa!(old)

■ 1000000個の素数

キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ring にて

mputさんの煽りにつられて、

というより単純なsieveで駄目なのか確かめたくて

sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]
printPrims 0 _      = return ()
printPrims c (x:xs) = print x >> printPrims (c-1) xs
main = printPrims 1000000 $ sieve [2..]

と定義してインタプリタでやとうとしたけど，待ちきれないかも．．．

でもメモリは平気だよ．

 % runhaskell 
 2
 3
 ...途中略
 556271
 556273
 556279
 556289
 ...

おそっ．だいたい幾つくらいなんだ，1000000番目の素数って？ 17000000 弱

かなぁ．おそすぎ，全然表示しきれないじゃん．まだ 1/30．だめだこりゃ．

でもメモリはだいじょうぶだと思うよ．

でも、ナイーブな実装ではあまりに遅いので高速版

main    = mapM print $ take 1000000 $ primes
primes  = 2:filter prime [3..]
prime n = all ((0/=) . mod n) $ takeWhile ((n>=) . s (*) id) primes
s f g x = f x (g x)

ちょっと待つけど，1000000番目の素数は 15485863 でした．