エラトステネスのふるいについて - 最古の素数のふるい
エラトステネスのふるいは、割り算を一度もせずに上限までのすべての素数を見つけます。数えるだけです: 2 の後は 2 つおきに、3 の後は 3 つおきに消し、これを続けます。残ったものが素数です。二千年以上たった今でも、素数を書き出す最も速い方法の 1 つです。
キュレネのエラトステネス
エラトステネスはおよそ紀元前 276 年から 194 年まで生き、アレクサンドリアの大図書館の館長を務めました。2 つの都市での影の長さから地球の大きさを測ったことで最もよく知られています。ふるいに彼の名前が付いているのは、ゲラサのニコマコスが紀元 100 年ごろに書いた『算術入門』でそれを彼の方法として紹介したからです。
ふるいの仕組み
2 から N までの数を書きます。最初の数 2 は素数です: 4、6、8 など 2 の倍数をすべて消します。残っている次の数 3 は素数です: 9、12、15 などを消します。5、7 と、その次に残っている数で続けます。一度も消されない数にはより小さい約数がないので、素数です。
平方根で止める
N までのすべての合成数は、N の平方根以下の素因数を持ちます。そのため p² が N を超えたら、もう消すものはありません。100 までの素数には 2、3、5、7 だけで足り、1000 までなら 31 までの素数で足ります。
どれくらい速いのか?
ふるいにはおよそ N log log N ステップかかり、これは N 自体よりわずかに速く増えるだけです。コンピューターは今でも、多くの場合は区分ふるいとして分割して、数十億までの素数を書き出すのに使っています。1 つの大きな数が素数かどうかを調べるには、他の方法のほうが速いです。
よくある質問
エラトステネスのふるいを考えたのは誰ですか?
紀元前 3 世紀のギリシャの学者、キュレネのエラトステネスにちなんで名付けられました。現存する最古の記述は、紀元 100 年ごろのゲラサのニコマコスによるものです。
なぜふるいは p² から消し始めるのですか?
p のより小さい倍数はすべてより小さい素因数を持つので、より小さい素数がすでに消しています。
1000 未満に素数はいくつありますか?
1000 未満には 168 個の素数があります。最大のものは 997 です。
関連ツール
エラトステネスのふるい
エラトステネスのふるいが 100、200、500、1000 までの素数を見つける様子を見てみましょう。各素数が自分の色で倍数を一歩ずつ消していきます。
ウラムの螺旋
ブラウザでウラムの螺旋を描きます。素数に印を付け、各対角線の二次式を読み取り、オイラーの途切れない40個の素数の列を開けます。
ウラムの螺旋
スタニスワフ・ウラムが1963年に描いた螺旋が整数をどう正方格子に並べるのか、なぜ素数が二次式の対角線に集まるのか、そして螺旋を41から始めたときオイラーの40個の素数がどこに並ぶのかを解説します。
コラッツ予想
ブラウザでコラッツの 3n+1 問題を探検しましょう。あられ数列をたどり、幾何学的なコラッツの木を育て、連続版コラッツ・フラクタルをズームできます。
試してみますか？
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エラトステネスのふるいを試す