エラトステネスの篩

デジタル大辞泉

エラトステネス‐の‐ふるい〔‐ふるひ〕【エラトステネスの^×篩】

読み方：えらとすてねすのふるい

古代ギリシャの学者エラトステネスが考案した素数の選別法。自然数を小さい順に並べ、まず1を消去し、次に2、3、5…と小さい方の素数を残してそれらの倍数を消去することで、最終的にある整数以下のすべての素数が得られる。

ウィキペディア

エラトステネスの篩

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/14 05:53 UTC 版)

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

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

アルゴリズム

2 から 120 までの数に含まれる素数を探すGIFアニメーション

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

ステップ 1

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

ステップ 2

配列の先頭から順に走査し、trueの要素を見つけたらその添字pを素数リストに追加し、配列の ${\displaystyle p^{2}}$

ウィキペディア小見出し辞書

エラトステネスの篩

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 06:15 UTC 版)

「メビウス関数」の記事における「エラトステネスの篩」の解説

既に知っている素数で割れる自然数を数表から篩い落とすことで新たな素数を順次決定していく操作はエラトステネスの篩として知られている。ゆえに、知っている素数で割れない自然数全体の集合を指定する方法が与えられることと、このエラトステネスの篩にかけることとは等価である。 集合を指定する方法の一つは、その指示函数を与えることである。いま、p1 から pk が素数として決定されたものとし、そのような素数全部の積を P とする。また、自然数 n と P との最大公約数を (n, P) と表せば、n が決定済みの素数で割れることと、(n, P) > 1 となることとは同値である。このとき、十分大きな自然数 N を考え、N 以下の自然数 n のうち、決定済みの素数 p1, ..., pk で割れない自然数全体の集合を E とおくと、基本公式によって E の指示函数 χE は χ E ( n ) = ∑ d ∣ ( n , P ) μ ( d ) で与えられることがわかるから、これをエラトステネスの篩のメビウス函数を用いた表現と考えることができる（手続きとしては、χE(n) を計算することは知っている素数で順番に割っていくことに他ならないから、単に表現の仕方を変えただけである）。特に、χE(n) = 1 を満たす最小の n を pk+1 とすればこれは新しい素数であり、再び同様の手続きにしたがって次々に素数を決定することができる。

Weblio日本語例文用例辞書

「エラトステネスの篩」の例文・使い方・用例・文例

• エラトステネスの篩という,素数を見い出す方法