エラトステネスの篩
砂場から小石を取り除く「ふるい」のように、余計な合成数を振り落として純粋な素数だけを残す数学の道具です。
定義 素数（1とその数自身でしか割り切れない1より大きい自然数）を素早く正確に見つけ出す、古代ギリシャの数学アルゴリズムです。まるで網目のふるいを使って砂だけを残し小石を取り除くように、小さな素数から順にその倍数を消していくことで、素数だけを綺麗に洗い出す方法です。
なぜ数を1つずつ割ってみないのでしょうか？
砂浜で砂の城を作るために、さらさらのきれいな砂を集めるときのことを思い浮かべてみてください。手で小石を1つずつ拾い集めるのは時間も手間もかかりますよね。代わりに網の目のついた「ふるい」に砂を入れてザルザルと振れば、大きくて粗い小石だけを一気に取り除くことができます。
数学で素数を見つけるときもまったく同じです。ある数が素数かどうか確かめるために、2から順にすべての数で1つずつ割り算していく方法は、数が大きくなるほど膨大な時間がかかってしまいます。1から100まで調べるだけでも、途方もない回数の割り算を繰り返さなければなりません。
古代ギリシャの学者エラトステネスは、この面倒な割り算の発想を根本から覆しました。数を1つずつ調べる代わりに、素数の倍数をまとめて消し去る「ふるい」を考案したのです。まず素数ではない「1」を除外した上で、最小の素数である「2」を見つけ、2以外の「2の倍数」をふるい落とすように一気に消すところからスタートします。
ふるいを振るように、倍数を順番に落としていきます
まず一番最初に残った「2」を素数として確定し、丸をつけます。そして、2以外の2の倍数である4、6、8、10といった偶数をすべて消します。「偶数」という巨大な小石の山を、たった1回ふるいを振るだけで一気に落としてしまったわけです。
次に、まだ消されずに残っている次の数「3」を素数として確定します。そして今度は、3以外の3の倍数である6、9、12、15などを順番に消していきます。6や12のようにすでに2の倍数として消えている数もありますが、9や15のような新たな合成数（素数以外の数）がふるい落とされます。
4はすでに消えているのでスキップし、次に残った「5」を素数に確定して5の倍数を消します。このように生き残った小さな数の倍数を消していく作業を繰り返すと、余計な合成数がすべて落ち、ふるいの上には純粋な素数だけが宝石のように残るのです。
もう少し正確に言うと — 最後まで調べる必要はありません
より正確に言えば、探したい範囲の最後まで、すべての数の倍数を消していく必要はまったくありません。探したい最大値の「平方根（ルート）」までの数を確認するだけで、素数の探索は完璧に完了するからです。
たとえば1から100までの自然数の中から素数を見つけたい場合、100の平方根である「10」以下の素数の倍数を消すだけで十分です。10より大きい素数である11や13の倍数は、それ以前の2、3、5、7の倍数を消すステップですでにすべて消されているからです。100以下の11の倍数（22、33、55、77など）は、すでにより小さな素数の倍数でもあるためです。
このスマートな近道のおかげで、計算の手間は劇的に削減されます。そのため現代のプログラミングでも、数万・数億といった膨大な範囲から素数のリストを一気に抽出する際には、数千年前の古代ギリシャで生まれたこの「ふるい落とし」アルゴリズムが今なお活躍しています。
🤔 よくある誤解
エラトステネスの篩は、ある1つの大きな数が素数かどうかを判定するのに最も適した方法である。
特定の大きな数が素数かどうかを1つだけ調べたいときは、別の素数判定法の方が効率的です。エラトステネスの篩は、「1から特定の範囲までのすべての素数のリスト」をまとめて一括で洗い出すときに最も威力を発揮します。
🧺 日常で出会う場面
数を1つずつ割り算するのではなく、素数の倍数を順番にふるい落とすことで、目的の範囲から素数だけを効率よく洗い出すアルゴリズムです。