エラトステネスの篩
出典: フリー百科事典『ウィキペディア（Wikipedia）』
数学において、エラトステネスの篩（エラトステネスのふるい）は素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
目次 |
[編集] アルゴリズム
[編集] ステップ 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
- 探索リスト：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
- 探索リスト：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
となる。
