エラトステネスの篩

海辺で砂のお城を作ろうと、きめ細かい砂を集めるときを思い浮かべてください。小石を手で一つひとつ拾い出すのは、時間もかかるし手間もかかります。その代わり、穴のたくさんあいた篩に砂を入れてゆすれば、大きくて粗い石だけを一度に落とせますよね。

数学で素数を探すときも同じです。ある数が素数かどうかを確かめるのに、2から始めてすべての数で順番に割ってみる方法では、数が大きくなるほど時間がかかりすぎます。1から100までだけでも、たくさんの割り算を繰り返さなければならないからです。

エラトステネスは、この面倒な割り算をまるごと発想転換しました。数を一つずつ調べる代わりに、素数の倍数をまとめて消してしまうふるいを作ったのです。1は素数ではないので先に外しておき、いちばん小さい素数である2を見つけたら、2の倍数を篩にかけるようにさっと消すところから探索を始めます。

まず生き残った2を素数と決めて、丸をつけます。そして、2を除く2の倍数である4、6、8、10のような偶数を全部消します。偶数という大きな小石の山を、たった一度の作業で篩の外に振り落とせたわけです。

次に、消されずに残っている次の数、3を素数と決めます。その後、3を除く3の倍数である6、9、12、15などを、篩から順に消していきます。6や12のようにすでに2の倍数として消えている数もありますが、9や15のように新しく振り落とされる合成数も出てきます。

4はもう消えているので飛ばして、次に残っている5を素数と決め、5の倍数を消します。このように残った小さい数の倍数を消していく作業を根気よく繰り返すと、合成数はすべて抜け落ち、最後には篩の上に純粋な素数だけが宝石のように残ります。

もう少し正確に言うと、探したい範囲の終わりまで、すべての数の倍数をいちいち消してみる必要はまったくありません。探したい最大値の平方根までだけ確認すれば、素数探しは完全に終わるからです。

たとえば100までの自然数から素数を探したいなら、100の平方根である10までの倍数を消せば十分です。10より大きい素数である11や13の倍数は、それ以前の段階、つまり2、3、5、7の倍数を消したときにすべて先に消えているからです。11の倍数のうち100以下の22、33、55、77のような数は、もっと小さい素数の倍数でもあります。

この賢い近道のおかげで、計算する量が劇的に減ります。そのためコンピュータのプログラミングでも、数万個、数億個にもなる巨大な範囲の素数リストを作るときに、何千年も前の古代ギリシャの学者が考え出したこのふるい分けのアルゴリズムと、それを磨き上げた改良版が、今でも中心的な技術として使われています。