エラトステネスの篩とは
古代ギリシャの数学者, エラトステネスが考案したとされる, 素数の判定法です.決められた自然数 以下のすべての素数を求めることができます.
アルゴリズム
以下の素数を求めたいとします.アルゴリズムの具体的な例(N=15 の場合)
15以下の素数を求めます.- を素数の候補の集合とします. はじめは, 2 ~ 15 のすべてが候補で, となります.
- 集合 の中で最小のもの 2 は素数です. を素数であると判定済みの数の集合として, とします. 2は素数と判定済み, 他の2の倍数は素数ではないので, から削除します. すると, .
- 同様に, の最小の数3を にうつして, 3の倍数をから削除します. , .
- の最小の数は5で, なので, この時点でに残っている数はすべて素数となり, にうつします.
アルゴリズムの説明
素数の候補の集合 の中で最小の数が素数になることは明らかです.( もし素数でなければ, 自分より小さいある素数で割り切れるので, 先にから削除されていなければならないので. )
そこで, の最小の数を素数として, その数の倍数をすべて削除することをくり返します.
以下の素数を求めたい場合, の最小の素数が を超えたときに残っている数は素数になります.
を超える素数の倍数で, 以下のものは, より なので, よりも小さい素数で割り切れることになり, すべて既に削除されているからです.