Problem 10

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

haskell

最初に書いたプログラムは70000までの素数の和程度でもいっぱいいっぱい。
『入門Haskell』にも載っていたProblem7(http://d.hatena.ne.jp/satzz/20080421/1208757141)の素数列生成コードを流用。

main = print $ sum $ 2 : (sieve [3,5..70000-1])
sieve []=[] 
sieve (x:xs) = x:sieve [z|z<-xs, z `mod` x /= 0]

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

こちらを参考に戦略を変えてみる。少し読みやすくしてみたつもり。

main   =print $ sum primes
primes =2:filter 
            (\n -> all (\x -> mod n x /= 0) $ takeWhile (\x -> x*x<=n) primes)
            [3,5..70000-1]

228890418

答えは同じですが、自分の環境で一つめは18秒かかるのに対し二つめは1秒。

why?

一つめ

1. 2の倍数でないもの(3,5,7,...)をsieveに渡す。
2. sieveは引数のうち3の倍数でないもの(5,7,11,13,...)をsieveに再帰的に渡す。
3. sieveは引数のうち5の倍数でないもの(7,11,13,17,...)をsieveに再帰的に渡す。
4. 引数が空になるまで繰り返す。

これはまさにエラトステネスのふるいですね。

二つめ

1. 整数を以下の条件primeでfilterしたものをprimesとする。
2. n<-primesがnの平方根以下の数で割り切れなければprime n=true

• n<-[3,5..70000-1]がnの平方根以下のprimesの要素で割り切れなければprime n=true

よくわからないのはprimesの定義が再帰になっていること。これはmapとか普通の関数の実装とは違う再帰な気がする。filterの挙動は

filter p xs=[x|x<-xs,p x]

リスト内包表記の挙動がわかればわかるかも。だけど

• リスト内包表記はdoのsugar
• つまりIOモナドのsugar

うーん。。。

answer

70000を2000000に変えると

142913828922

これで30秒程度。
実は

[3..2000000]

でもあまりかわらない。

一日一チベットリンク

北京五輪は８月８日の開幕まで、３０日であと１００日となる。運営面の準備に大きな遅れはないが、中国のチベット暴動鎮圧に絡み、世界各地を巡った聖火リレーは抗議や妨害行動で混乱。中国国内での排外的「愛国心」の盛り上がりといった新たな懸念が生まれるなど、スポーツの一大祭典らしくない話題が続いている。