エラトステネスの篩(エラトステネスノふるい)とは | 意味や読み方など丁寧でわかりやすい用語解説

エラトステネスの篩は、指定された自然数Nまでの全ての素数を効率的に発見するための、古典的かつ非常に有名なアルゴリズムである。古代ギリシャの数学者であり天文学者でもあったエラトステネスによって考案された。このアルゴリズムの名称は、素数ではない合成数を「篩（ふるい）」にかけて次々と落としていき、最終的に素数だけを残すという、その処理内容の様子に由来する。単純な方法で素数を一つずつ判定していくのに比べ、一定範囲内の素数をまとめて見つけ出す場合に極めて高速に動作するため、計算機科学の分野やプログラミングの学習において、基本的なアルゴリズムの一つとして広く扱われている。システム開発においても、暗号技術の基礎や数値計算の分野で素数リストが必要となる場面があり、その考え方を理解しておくことは有益である。

このアルゴリズムの具体的な手順は、非常に直感的で理解しやすい。まず、素数を見つけたい範囲の終わりとなる数Nを定める。次に、2からNまでの整数を昇順に並べたリストを用意する。この時点では、リストに含まれるすべての数が素数の候補となる。プログラムで実装する際は、通常、大きさN+1の真偽値型の配列を用意し、全ての要素を「真」（素数候補である）で初期化することが多い。ただし、0と1は素数ではないため、あらかじめ除外しておく。処理の開始点は、最初の素数である2からとなる。まず、2を素数として確定させる。次に、リストの中から、確定した素数である2自身を除く、2の倍数（4, 6, 8, 10などN以下の数）を全て探し出し、それらをリストから削除するか、あるいは「偽」（素数ではない）という印をつける。これらの数は2で割り切れるため、定義上、素数ではありえないからだ。続いて、リストを先頭から見ていき、まだ削除されていない（「真」の印がついている）次の数を探す。この場合、3が見つかる。3を新たな素数として確定させ、先ほどと同様に、3自身を除く、3の倍数（6, 9, 12, 15などN以下の数）を全てリストから削除、または印をつける。このとき、6のように既に2の倍数として削除されている数も対象となるが、再度処理しても問題はない。この「まだ削除されていない最小の数を見つけて素数と確定し、その倍数を全て削除する」という操作を繰り返していく。3の次に見つかるのは5であり、5を素数として確定させ、その倍数を削除する。その次は7、11と続いていく。この篩い落とす作業をどこまで続ければよいかという点には、重要な効率化のポイントがある。篩にかける素数は、Nの平方根（√N）以下のものだけで十分である。なぜなら、N以下の 어떤合成数kは、必ず√k以下の素因数を持つからだ。kはN以下なので、√kも√N以下となる。したがって、N以下の全ての合成数は、√N以下のいずれかの素数の倍数として必ず篩い落とされることになる。この性質により、探索範囲を大幅に限定でき、計算時間を劇的に短縮することが可能となる。この繰り返し処理が完了したとき、リスト上に削除されずに最後まで残った数（「真」の印がついたままの数）が、2からNまでの全ての素数となる。エラトステネスの篩は、特定の数が素数かどうかを単発で判定する「素数判定」よりも、ある範囲の素数を網羅的にリストアップする「素数生成」において、その真価を発揮するアルゴリズムである。その計算量は、O(N log log N)と評価され、Nまでの各数について素数判定を繰り返す単純な方法よりもはるかに高速である。ただし、2からNまでの数値を保持するためのメモリ領域が必要となるため、Nが非常に大きくなるとメモリ使用量が課題となる場合がある。これは、計算速度とメモリ使用量がトレードオフの関係にある典型的な例と言える。