エラトステネスの篩

エラトステネスの篩（エラトステネスのふるい）は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

アルゴリズム

以下では2 から 20 までの数に含まれる素数をさがす。右のアニメーションでは以下のステップにそって2 から 120 までの数に含まれる素数をさがしている。

ステップ 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

となる。

理論的考察

エラトステネスの篩は $x^{1/2}$ 以下の素数が既知のとき、（$x^{1/2}$ 以上）x 以下の素数を決定するには、x 以下の整数で $x^{1/2}$ 以下の素数の倍数を全て取り除けば（= 篩えば）よいことを意味する。このことから、包除原理を用いることによって x 以下の素数の個数に関する式を得ることができる。

具体的な式を書くために、いまx 以下の素数の個数を $\pi(x)$ と書き、z 以下の全ての素数の積を $P=P(z)$ とすると、この篩の操作が与える定量的な公式は

$\pi(n)-\pi \left(\sqrt{n}\, \right)+1=\sum_{d\mid P(\sqrt{n})} \! \mu(d)\left[\frac{\,x\,}{d}\right]$

となる（左辺の +1 は篩われずに残る数 {1} の分である）。

より一般に、整数の集合A から、z 以下の素数の倍数全てを篩うとき、残る元の個数 $S(A,P)$ は、

$S(A,P)=\sum_{d\mid P(z)}\!\mu(d) \left| A_{d\,} \right|$

と表すことができる。ここで $A_d$ は A の元で d で割り切れるもの全体の集合を表す。この定式化はルジャンドルの篩ともよばれる。

再び先の素数の個数の評価について述べれば、$z\leq\sqrt{n}$ のとき、不等式

$\pi(n) - \pi(z) + 1 \leq \sum_{d\mid P(z)} \! \mu(d)\left[\frac{\,n\,}{d}\right]$

が成り立つから、不等式 $\left| \left[\frac{\,n\,}{d}\right] - \frac{\,n\,}{d} \right| \leq1$ を用いて

$\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)}$

という評価が得られる。この公式から（$z = \log n$ とおき、素数の逆数の和が発散することを用いて）

$\lim_{x\to \infin}\! \frac{\,\pi (x)\,}{x} = 0$

を証明することができる。

しかし、其評価の過程で上の $2^{\pi (z)}$ のような大きな誤差項が現れてしまうのは、包除原理にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の篩法である。この方法は双子素数予想など、多くの数論上の問題の研究に広く応用されている。

関連項目

• 篩法