HaHaHa!(old)

2006-06-17

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 でした.

jmkjmk2006/06/17 08:49100,000個までは計算させてみました。メモリは大丈夫っぽいのですが、遅すぎました(2時間くらいかかりました)。1,000,000個だとどんだけ時間がかかるのかと。

FlorenceFlorence2013/07/29 20:40You mean I don't have to pay for expert advice like this anme?ryo!

VegaVega2013/07/31 00:11Just cause it's simple doesn't mean it's not super <a href="http://msojlj.com">hefplul.</a>

RupeshRupesh2013/07/31 05:03I read your post and wihsed I was good enough to write it http://ewjhbevytn.com [url=http://boegmolr.com]boegmolr[/url] [link=http://rqqwfalt.com]rqqwfalt[/link]