|
|
| (同じ利用者による、間の1版が非表示) |
| 1行目: |
1行目: |
| − | '''エラトステネスの篩''' (エラトステネスのふるい、{{lang-en-short|''Sieve of Eratosthenes''}}) は、指定された[[整数]]以下の全ての[[素数]]を発見するための単純な[[アルゴリズム]]である。[[古代ギリシア]]の科学者、[[エラトステネス]]が考案したとされるため、この名がある。 | + | '''エラトステネスの篩''' (エラトステネスのふるい、{{lang-en-short|''Sieve of Eratosthenes''}}) |
| | | | |
| − | == アルゴリズム ==
| + | 古代ギリシャの学者エラトステネスが考案した素数の選別法。自然数を小さい順に並べ、まず1を消去し、次に2、3、5…と小さい方の素数を残してそれらの倍数を消去することで、最終的にある整数以下のすべての素数が得られる。 |
| − | [[ファイル:Animation Sieb des Eratosthenes.gif|right|2 から 120 までの数に含まれる素数をさがすGIFアニメーション]]
| |
| − | 指定された整数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> のような大きな誤差項が現れてしまうのは、[[包除原理]]にのみに依拠した式の共通の欠点である。このような困難を回避し、より一般的な状況で篩われた集合の元の個数を近似・評価するのが現代の[[篩法]]である。この方法は[[双子素数予想]]など、多くの数論上の問題の研究に広く応用されている。
| |
| − | | |
| − | ==関連項目==
| |
| − | *[[篩法]]
| |
| − | *[[幸運数]] - エラトステネスの篩に似た方法で選ばれる自然数
| |
| − | *{{仮リンク|アトキンの篩|en|Sieve of Atkin}} - より現代的で高速なアルゴリズム
| |
| − | *[[Eテレ0655&2355|2355]] - 2から100までの場合の解説を歌（[[中尾ミエ]]）にしたものを放送している。
| |
| | | | |
| | {{デフォルトソート:えらとすてねすのふるい}} | | {{デフォルトソート:えらとすてねすのふるい}} |
| 79行目: |
10行目: |
| | [[Category:素数]] | | [[Category:素数]] |
| | [[Category:エポニム]] | | [[Category:エポニム]] |
| | + | {{テンプレート:20180815sk}} |