project euler problem 10

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

昨日取得した素数列を生み出す関数ですぐ終わると思ったが計算時間が半端じゃなかった

main=print $ sum $takeWhile (<2000000) primes

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

だめだ。このアルゴリズムだとスタックオーバーフローだ。

$ time ./a.out
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

real:483m33.969s,user:483m18.400s,sys:0m17.361s
$ free
             total       used       free     shared    buffers     cached
Mem:       2061216    1866800     194416          0     422980    1222672
-/+ buffers/cache:     221148    1840068
Swap:      9765616          0    9765616

もうすこしスワップのあるマシンにしよう。
あと、2以上の奇数でのみ行うことにしてと…

$ cat 10-2.hs
main=print $ sum $ takeWhile (<2000000) primes
primes = sieve (2:[3,5..])
sieve (p:xs) = p:[x|x<-sieve xs,mod x p/=0]
$ time ./10-2
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

real:583m8.805s,user:582m47.733s,sys:0m23.197s

くぅこれでもだめだ

エラトステネスの篩は x1 / 2 以下の素数が既知のとき、（x1 / 2 以上）x 以下の素数を決定するには、x 以下の整数で x1 / 2 以下の素数の倍数を全て取り除けば（＝篩えば）よいことを意味する。このことから、包除原理を用いることによって x 以下の素数の個数に関する式を得ることができる。

なんと…√2以下で行うのがエラトステネスの篩じゃん…
内包表記で√２以下に限定する方法がわからない…どんなガードを書けばいいんだろう…

main=print $ sum $ takeWhile (<2000000) primes

primes = 2:filter isPrime [3,5..]
isPrime n = all (\x->mod n x/=0) $ takeWhile (\x->x^2<=n) primes

無限に呼び合う二つの再帰関数か。むずかしい。

$ time ./a.out
142913828922

real:0m19.820s,user:0m19.789s,sys:0m0.032s

よし。できた。
でも内包表記ではまだわからない。