エラトステネスの篩

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

アルゴリズム

指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から 120 までの数に含まれる素数をさがしている。

ステップ 1

120要素の配列の1番目にfalseを、2番目以降に全てtrueを入れる。

ステップ 2

配列の先頭から順に走査し、trueの要素を見つけたらその添字pを素数リストに追加し、配列の $p^{2}$ 以上のpの倍数番目をfalseにする。

ステップ 3

上記の篩い落とし操作を、走査している要素の添字がxの平方根に達するまで行う。

ステップ 4

最後までtrueだった要素の添字を素数リストに追加して処理終了。

具体例　x=120 の場合

配列の中身は、trueである添字がどれかを表記。残りは全てfalseである。

ステップ 1: 配列={2から120まで}、探索リストの先頭値=2
ステップ 2-1: 素数リスト={2}; 配列={3から119までの奇数}、探索リストの先頭値=3
ステップ 2-2: 素数リスト={2,3}; 配列={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}; 配列={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}; 配列={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: 次の素数が ${\sqrt {120}}=10.954\cdots$ に達しているのでステップ4へ
ステップ 4: 11以上の、trueである要素の添字を素数リストに追加; 素数リスト={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}

理論的考察

エラトステネスの篩（ふるい）は $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)=\sum _{d\mid P({\sqrt {n}})}\!\mu (d)(\left[{\frac {\,n\,}{d}}\right]-\left[{\frac {\sqrt {n}}{d}}\right])

となる（ $\mu (d)$ はメビウス関数）。

より一般に、整数の集合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|\leq 1$ を用いて

\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 \infty }\!{\frac {\,\pi (x)\,}{x}}=0

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

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

外部リンク

『エラトステネスのふるいとその計算量』 - 高校数学の美しい物語