エラトステネスの篩とは？
えらとすてねすのふるい
エラトステネスの篩とは、古代ギリシャで考案された、一定の範囲内の素数をすべて列挙するための篩いわけアルゴリズムです。
エラトステネスの篩（ふるい）とは、ある整数N以下のすべての素数を効率的に求めるためのアルゴリズムです。古代ギリシャの数学者エラトステネス（紀元前3世紀頃）が考案したとされ、2000年以上の歴史を持つ最古のアルゴリズムの一つです。
アルゴリズムの手順は以下のとおりです。
- 2からNまでの整数をすべて書き出す
- 最初の数2は素数とし、2の倍数（4, 6, 8, …）をすべて消す
- 次に残った最小の数3を素数とし、3の倍数をすべて消す
- 次の残った数5を素数とし、5の倍数を消す
- √N以下の数まで繰り返すと、消えずに残った数がすべて素数
このアルゴリズムの時間計算量はO(N log log N)であり、Nが比較的小さい場合には非常に高速に素数を列挙できます。実装が簡単で直感的に理解しやすいため、プログラミングの入門課題としてもよく取り上げられます。
現代では、より大きな数の素数判定には他のアルゴリズム（ミラー-ラビン素数判定法など）が使われますが、エラトステネスの篩は特定範囲内の素数を一括生成する用途では今でも標準的な手法です。暗号理論や数論的な計算プログラムで実用的に用いられています。
使い方・例文
プログラミングで「100以下の素数をすべて出力せよ」という問題を解くとき、エラトステネスの篩を実装するとシンプルな繰り返し処理だけで2, 3, 5, 7, 11, …と効率よく素数を列挙できます。
この用語をシェア
最終更新: