エラトステネスの篩 - projectpn

エラトステネスの篩は昔から知られている素数列挙アルゴリズムである。

入力:列挙する素数の上限 n(n > 2)
出力:2からnまでの素数のリスト
ステップ1
2からnまでの自然数を列挙した探索リストを作成する。このとき素数リストは空である。
ステップ2
素数リストに探索リストの中で最小の数aを入れ、探索リストからaの倍数を消す。
ステップ3
aの自乗がnより小さい場合はステップ2に戻る。そうでない場合は探索リストに残っている数を素数リストに入れ、素数リストを出力する。

実行時間

このアルゴリズムの計算量のオーダーはリストへのランダムアクセスがと仮定するとである。これは入力データのサイズ(nの桁数)に対して指数時間以上のオーダーであり、単一の数の素数判定に用いられる多項式時間オーダーのアルゴリズムに比べると非常に遅いが、大量の数の素数判定を行うときには、最初にかけてリストを作っておけば各クエリに対してで答えることができる。