エラトステネスのふるい

デジタル大辞泉

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

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

古代ギリシャの学者エラトステネスが考案した素数の選別法。自然数を小さい順に並べ、まず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}}$