数学において、エラトステネスの篩（エラトステネスのふるい）は素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

アルゴリズム

---

ステップ 1

整数を 2 から昇順で探索リストに羅列する。

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ステップ 2

リストの先頭の数を素数リストに記録する。

素数リスト：2

探索リスト：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

ステップ 3

前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。

素数リスト：2

探索リスト：3 5 7 9 11 13 15 17 19

ステップ 4

探索リストの最大数が素数リストの最大数の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大数が素数リストの最大数の平方よりも大きい場合、ステップ 2 に戻る。

19 は 2 の平方よりも大きいので、ステップ 2 に戻る。

ステップ 2

素数リスト：2 3

探索リスト：5 7 9 11 13 15 17 19

ステップ 3

素数リスト：2 3

探索リスト：5 7 11 13 17 19

ステップ 4

19 は 3 の平方よりも大きいので、ステップ 2 に戻る。

ステップ 2

素数リスト：2 3 5

探索リスト：7 11 13 17 19

ステップ 3

素数リスト：2 3 5

探索リスト：7 11 13 17 19

ステップ 4

19 は 5 の平方よりも小さいので、リストに残っている数が素数である。

結果：2 から 20 までの数に含まれる素数は、

2 3 5 7 11 13 17 19

数論 | アルゴリズム | 初等数学

Решето на Ератостен | Eratosthenovo síto | Sieb des Eratosthenes | Sieve of Eratosthenes | Criba de Eratóstenes | Eratostheneen seula | Crible d'Ératosthène | הנפה של ארטוסתנס | Crivello di Eratostene | Eratosteno rėtis | Zeef van Eratosthenes | Sito Eratostenesa | Решето Эратосфена | Sieve of Eratosthenes | Eratostenovo sito | Eratostenovo sito | Eratosthenes såll | 埃拉托斯特尼筛法