Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

自分が実装したエラトステネスのふるいは遅かった。単純な素数生成。

p010 = sum$takeWhile(<2000000)$primes
primes = 2:filter isPrime [3,5..]
isPrime x = all ((/= ).mod x)$takeWhile (<= (floor.sqrt.fromIntegral$ x)) primes

エラトステネス改良

ふるいの実行途中でpが素数だと分かると、のこっているp*p以下の数も素数である

これを各pについて行う、このとき無駄な割り算をしないようにする。

(qsに対しては割り算はpでのみ、psでは行わない。次のステップで得られる素数から

割り算を実行せずとも素数であることが分かるやつがいる。)

多分こっちのほうがはやい。

sieve' (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=).(`mod` p)) qs'))
where (ps',qs') = span (<p*p) qs
primes' = iterate sieve'([2,3],([3],[3,5..]))>>=fst
More Reading
Newer// Problem 24
Older// Problem 11