10未満の素数の和は2+3+5+7=17である。
200万未満の素数の和を求めよ。
問題自体は単なる計算問題である。しかし、ここまでくると問題2の定義では素 数の計算が遅すぎてどうしようもなくなってくる。ここで少しだけ素数の計算 の高速化を考える。まずはエラトステネスの篩のアルゴリズムを振り返ってみ る。2が素数なので2以上の数のうち2の倍数を除外する。このとき3は除外され てないので素数である。次に3が素数なので3以上の数のうち3の倍数を除外する。 4は2の倍数で除外されているが5は除外されていないので素数である。次に5の 倍数をという風に素数の倍数をふるい落とすことで残った数が全て素数になる というのがアルゴリズムの大まかな説明となる。
このアルゴリズムは素数を求めたい対象となる数の上限があらかじめ決まって いて、例えばそのbit配列に対して、既に求まった素数の倍数にあたる部分を チェックしていくような実装にした場合非常に高速である。
ここでHaskellで実行を考える。Haskellでは素数が無限のリストとして表され るが、当然無限のリストから2の倍数を全て除外することはできない。したがっ て実際には必要に応じて2の倍数なら除外する関数のようなものを内部的に生成 することになる。3の場合や5の場合も同様である。こういった後で計算するた めの内部的な構造のことはthunkと呼ばれている。
ここで実際にn番目の素数の値を使う場面を考えてみると、n-1番目までの素数 の倍数かどうかを試すthunk を全て実行して素数かどうかの判定をすることに なる。やっている処理自体は不自然ではない。n番目の素数というのはn-1番目 までのどの素数の倍数にもなっていないものである。しかし、それがエラトス テネスの篩的に実装されているためにn-1番目までの素数の倍数かどうかのチェッ クがそれぞれの別々のthunk になっているのは大きなオーバーヘッドである。
ここで、実際の処理を素直に表現したような書き方で素数primesを書き直す。 候補となる数列に対して素数かどうかのチェックをする関数isPrimeをfilterで 適用する。これによって少なくとも一つの素数のチェックに必要な関数適用は 一つに減らすことができる。また倍数かどうかのチェックもひとつ前の素数ま でではなく、nの平方根以下の素数までのチェックにできる。すべての素数で割 り切れないことのチェックはall関数を用いて以下のようにかける。
primes = 2 : filter isPrime [3, 5..]
where isPrime n = all (\x -> n `mod` x /= 0)
$ takeWhile (\x -> x * x <= n) primes
euler010 = sum $ takeWhile (<= 2000000) primes