エラトステネスの篩

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