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 ((/= 0).mod x)$takeWhile (<= (floor.sqrt.fromIntegral$ x)) primes

エラトステネス改良
ふるいの実行途中でpが素数だと分かると、のこっているp*p以下の数も素数である
これを各pについて行う、このとき無駄な割り算をしないようにする。
（qsに対しては割り算はpでのみ、psでは行わない。次のステップで得られる素数から
割り算を実行せずとも素数であることが分かるやつがいる。）
多分こっちのほうがはやい。

sieve' (_,((p:ps),qs)) = (ps',(ps++ps',filter ((/=0).(`mod` p)) qs'))
    where (ps',qs') = span (<p*p) qs
primes' = iterate sieve'([2,3],([3],[3,5..]))>>=fst