エラトステネスの篩のソースを表示

{{出典の明記|date=2019-06}}
'''エラトステネスの篩''' (エラトステネスのふるい、{{lang-en-short|''Sieve of Eratosthenes''}}) は、指定された[[整数]]以下の全ての[[素数]]を発見するための単純な[[アルゴリズム]]である。[[古代ギリシア]]の科学者、[[エラトステネス]]が考案したとされるため、この名がついている。

== アルゴリズム ==
[[画像:Animation Sieb des Eratosthenes.gif|right|2 から 120 までの数に含まれる素数を探すGIFアニメーション]]
指定された整数x以下の全ての素数を発見するアルゴリズム。このアニメーションでは以下のステップにそって 2 から 120 までの数に含まれる素数をさがしている。

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

=== ステップ 2 ===
配列の先頭から順に走査し、trueの要素を見つけたらその添字pを素数リストに追加し、配列の <math>p^2</math> 以上の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
: 次の素数が <math>\sqrt{120}=10.954\cdots</math> に達しているのでステップ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}

== 理論的考察 ==
エラトステネスの{{ruby|篩|ふるい}}は <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)=\sum_{d\mid P(\sqrt{n})} \! \mu(d)(\left[\frac{\,n\,}{d}\right]-\left[\frac{\sqrt{n}}{d}\right])</math>
となる（ <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> のような大きな誤差項が現れてしまうのは、[[包除原理]]にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の[[篩法]]である。この方法は[[双子素数予想]]など、多くの数論上の問題の研究に広く応用されている。

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

== 外部リンク ==
*{{高校数学の美しい物語|992|エラトステネスのふるいとその計算量}}


{{DEFAULTSORT:えらとすてねすのふるい}}
[[Category:数論]]
[[Category:初等数学]]
[[Category:エラトステネス]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]
[[Category:素数判定]]
[[Category:算数]]