素数を一瞬で見つける！エラトステネスのふるい超入門

数字の世界の「ぼっち」を探せ！素数ハンターの心得
割り算はしない！倍数をまとめてゴミ箱へポイ
プログラミングの世界で大絶賛される理由
実際にコードで書いてみよう
まとめ：先人の知恵を借りて賢くサボろう

数字の世界の「ぼっち」を探せ！素数ハンターの心得

世の中には、これ以上バラバラに分解できない「孤高の数字」が存在します。

それが素数です。

具体的には「1とその数字自身」でしか割り切れない、ちょっと頑固な数字たちのことです。たとえば「2、3、5、7」などがこれに当たります。「6」は「2×3」に分解できるので素数ではありません。

プログラムの試験や数学の宿題で「1から100までの間にある素数をすべて書き出しなさい」と言われたら、あなたならどうしますか。

「2は素数。3も素数。4は2で割れるからダメ。5は素数。6は……」

こんな風に、1つずつ真面目に割り算を繰り返すのは時間のムダです。数が大きくなればなるほど、脳のメモリが爆発します。

そこで登場するのが、今から2000年以上前の天才が編み出した「エラトステネスのふるい」というチート技です。

割り算はしない！倍数をまとめてゴミ箱へポイ

この方法の素晴らしいところは、面倒な割り算を「一回もしない」点にあります。

やることはシンプルです。

「素数の倍数」を、順番に塗りつぶして消し去る。

これだけです。まるで、学校のプリントで提出していない人の名前を名簿からまとめて消していくような、爽快な作業です。

具体的な手順を実況中継します。1から20までの数字から、素数だけを生き残らせてみましょう。

ステップ1：まずは「1」を即退場させる

1は法律（定義）により素数にはなれません。問答無用で消去します。

ステップ2：「2」を残して、2の倍数をすべて消す

生き残っている中で一番小さい数字は「2」です。これは確定で素数です。そしたら、2の親戚である「4、6、8、10、12、14、16、18、20、…」と偶数たちをすべて消します。

これらはすべて2で割り切れるため、素数になる資格はありません。

ステップ3：次に生き残っている「3」を残して、3の倍数を消す

次に生き残っているのは「3」です。これも素数です。今度は3の倍数である「6、9、12、15、18、…」を消します。

6や12などすでに消えている数字もありますが、気にせず残りを消します。

ステップ4：さらに次に生き残っている「5」を残して、5の倍数を消す

次にいるのは「5」です。これも素数です。 5の倍数である「10、15、20」を消します。

これを繰り返していくと、最終的に消されずに生き残った数字だけが手元に残ります。

それが「2、3、5、7、11、13、17、19」です。

おめでとうございます。一切割り算をすることなく、見事に素数だけをあぶり出すことに成功しました。

プログラミングの世界で大絶賛される理由

なぜ、この大昔のやり方が現代のITの世界でも大活躍しているのでしょうか。

理由は単純で、コンピューターにとって「割り算」は非常にエネルギーを使う重い作業だからです。

もし1から100万までの数字を1つずつ割り算して素数かどうかチェックさせると、パソコンは一瞬フン詰まりを起こします。内部で膨大な計算がグルグル回るためです。

しかし、エラトステネスのふるいを使えば、コンピューターは「足し算」だけで処理を済ませられます。2の倍数なら「2、4、6、8……」と2を足していくだけで消去リストを作れます。

コンピューターにとって、足し算は朝飯前です。圧倒的なスピードで処理が終わります。

効率的なプログラムを作るための、お手本のような仕組みです。

実際にコードで書いてみよう

この仕組みを、実際のプログラム（PHP）で書くとこうなります。 100までの数字から素数を見つけるコードです。

<?php
$limit = 100;
$isPrime = array_fill(0, $limit + 1, true);
$isPrime[0] = $isPrime[1] = false; // 0と1は素数ではない

for ($i = 2; $i <= sqrt($limit); $i++) {
    if ($isPrime[$i]) {
        for ($j = $i * $i; $j <= $limit; $j += $i) {
            $isPrime[$j] = false; // iの倍数を消す
        }
    }
}

$primes = [];
for ($n = 2; $n <= $limit; $n++) {
    if ($isPrime[$n]) {
        $primes[] = $n;
    }
}

echo implode(", ", $primes) . "\n";Code language: HTML, XML (xml)