3は2で割り切れる数ではありませんでした。そのため、3には何も記録されていません。そこで、3を素数として記録します。将来的に処理するであろう3の整数倍の数も全て素数ではありません。先ほどと同様に、これも記録しましょう。次に4を処理しますが、4は「素数ではない」と記録されています。そのため、単純にスキップします。5には何も記録されていないため、素数です。3と同様の処理をします。6からもこれを繰り返します。説明では「記録されていない」、「素数である」、「素数ではない」の3つの状態を考えていますが、実際には「素数である」、「素数ではない」の2つの状態のみを扱えばアルゴリズムとして成立します。その場合、初めに記憶領域は全て「素数である」の状態にしておきます。ここまでを実装に反映したものが以下です。:その効果は絶大で、Nが106で0.11秒で終わるようになりました。続けて7を処理した状態を考えてみましょう。先ほどの実装では7に続き、11、13、...と処理していますが、実はその必要はありません。Nまでの素数を調べるのに2〜√Nまでを調べればよいのはエラトステネスの櫛も同様なのです。ここではNを120としていますので、√Nは10.95ほどです。そのため、10まで考えればいいことになります。120に近い113について考えてみましょう。√113は10.63です。先ほど計算した10.95よりも小さいですね。同様に、109、107、...、11までの平方根はそれぞれ11よりも小さいので、やはり高々10までを調べれば十分なのです。今ひとつピンと来ない人には以下のように形式的に記述したもののほうが分かりやすいかもしれません。ここまでの考察を元に、エラトステネスの篩の最終版を実装します。Eratosthenesによれば計算量はO(NloglogN)だそうです。実装も随分簡素になりました。速度も速く、Nが106のときは0.006秒で終わるようになりました。Nが107であっても0.05秒ほどで終わり、108であっても0.74秒で終わります。Prime素数を扱う簡単なアルゴリズムはO(√n)で行えます。Programming(1...昨年のSIGGRAPH参加後、9月ほどからでしょうか。