エラトステネスの篩
エラトステネスの篩 (エラトステネスのふるい、英: Sieve of Eratosthenes) は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。
アルゴリズム
指定された整数x以下の全ての素数を発見するアルゴリズム。右のアニメーションでは以下のステップにそって2 から 120 までの数に含まれる素数をさがしている。
ステップ 1
探索リストに2からxまでの整数を昇順で入れる。
ステップ 2
探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
ステップ 3
上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
ステップ 4
探索リストに残った数を素数リストに移動して処理終了。
具体例 x=120 の場合
- ステップ 1
- 探索リスト={2から120まで}、探索リストの先頭値=2
- ステップ 2-1
- 素数リスト={2}
- 探索リスト={3から119までの奇数}、探索リストの先頭値=3
- ステップ 2-2
- 素数リスト={2,3}
- 探索リスト={5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97,101,103,107,109,113,115,119}
- 探索リストの先頭値=5
- ステップ 2-3
- 素数リスト={2,3,5}
- 探索リスト={7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113,119}
- 探索リストの先頭値=7
- ステップ 2-4
- 素数リスト={2,3,5,7}
- 探索リスト={11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113}
- 探索リストの先頭値=11
- ステップ 3
- 探索リストの先頭値が [math]\sqrt{120}=10.954\cdots[/math] に達しているのでステップ4へ
- ステップ 4
- 残った探索リストを素数リストに移動
- 素数リスト={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113}
理論的考察
エラトステネスの篩は [math]x^{1/2}[/math] 以下の素数が既知のとき、（[math]x^{1/2}[/math] 以上）x 以下の素数を決定するには、x 以下の整数で [math]x^{1/2}[/math] 以下の素数の倍数を全て取り除けば（= 篩えば）よいことを意味する。このことから、包除原理を用いることによって x 以下の素数の個数に関する式を得ることができる。
具体的な式を書くために、いまx 以下の素数の個数を [math]\pi(x)[/math] と書き、z 以下の全ての素数の積を [math]P=P(z)[/math] とすると、この篩の操作が与える定量的な公式は
- [math]\pi(n)-\pi \left(\sqrt{n}\, \right)+1=\sum_{d\mid P(\sqrt{n})} \! \mu(d)\left[\frac{\,x\,}{d}\right][/math]
となる（左辺の +1 は篩われずに残る数 {1} の分で、 [math]\mu(d)[/math] はメビウス関数）。
より一般に、整数の集合A から、z 以下の素数の倍数全てを篩うとき、残る元の個数 [math]S(A,P)[/math] は、
- [math]S(A,P)=\sum_{d\mid P(z)}\!\mu(d) \left| A_{d\,} \right|[/math]
と表すことができる。ここで [math]A_d[/math] は A の元で d で割り切れるもの全体の集合を表す。この定式化はルジャンドルの篩ともよばれる。
再び先の素数の個数の評価について述べれば、[math]z\leq\sqrt{n}[/math] のとき、不等式
- [math] \pi(n) - \pi(z) + 1 \leq \sum_{d\mid P(z)} \! \mu(d)\left[\frac{\,n\,}{d}\right] [/math]
が成り立つから、不等式 [math]\left| \left[\frac{\,n\,}{d}\right] - \frac{\,n\,}{d} \right| \leq1[/math] を用いて
- [math] \pi(n) \, \leq \, \pi(z) + \sum_{d\mid P} \left( \mu(d)\frac{\,n\,}{d} + 1 \right) \, = \,\pi(z) + n\sum_{d\mid P} \frac{\mu(d)}{d} + \sum_{d\mid P}1 \,=\, \pi(z) + n\prod_{p\leq z} \left( 1 - \frac{1}{\,p\,} \right) + 2^{\pi(z)} [/math]
という評価が得られる。この公式から（[math]z = \log n[/math] とおき、素数の逆数の和が発散することを用いて）
- [math] \lim_{x\to \infin}\! \frac{\,\pi (x)\,}{x} = 0 [/math]
を証明することができる。
しかし、其評価の過程で上の [math]2^{\pi (z)}[/math] のような大きな誤差項が現れてしまうのは、包除原理にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の篩法である。この方法は双子素数予想など、多くの数論上の問題の研究に広く応用されている。