エラトステネスの篩 (エラトステネスのふるい、) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。指定された整数x以下の全ての素数を発見するアルゴリズム。右のアニメーションでは以下のステップにそって2 から 120 までの数に含まれる素数をさがしている。探索リストに2からxまでの整数を昇順で入れる。探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。探索リストに残った数を素数リストに移動して処理終了。エラトステネスの篩は formula_2 以下の素数が既知のとき、（formula_2 以上）"x" 以下の素数を決定するには、"x" 以下の整数で formula_2 以下の素数の倍数を全て取り除けば（= 篩えば）よいことを意味する。このことから、包除原理を用いることによって "x" 以下の素数の個数に関する式を得ることができる。具体的な式を書くために、いま"x" 以下の素数の個数を formula_5 と書き、"z" 以下の全ての素数の積を formula_6 とすると、この篩の操作が与える定量的な公式はとなる（左辺の +1 は篩われずに残る数 {1} の分である）。より一般に、整数の集合"A" から、"z" 以下の素数の倍数全てを篩うとき、残る元の個数 formula_8 は、と表すことができる。ここで formula_10 は "A" の元で "d" で割り切れるもの全体の集合を表す。この定式化はルジャンドルの篩ともよばれる。再び先の素数の個数の評価について述べれば、formula_11 のとき、不等式が成り立つから、不等式 formula_13 を用いてという評価が得られる。この公式から（formula_15 とおき、素数の逆数の和が発散することを用いて）を証明することができる。しかし、其評価の過程で上の formula_17 のような大きな誤差項が現れてしまうのは、包除原理にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の篩法である。この方法は双子素数予想など、多くの数論上の問題の研究に広く応用されている。

出典:wikipedia