エラトステネスの篩

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "エラトステネスの篩" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年6月)

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

アルゴリズム

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

理論的考察

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \lim _{x\to \infty }\!{\frac {\,\pi (x)\,}{x}}=0}$

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

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

関連項目

• 篩法
• 幸運数 - エラトステネスの篩に似た方法で選ばれる自然数
• サンダラムの篩
• アトキンの篩 - より現代的で高速なアルゴリズム
• Eテレ0655&2355 - 2から100までの場合の解説を歌（中尾ミエ）にしたものを放送している。

外部リンク

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