エラトステネスの篩って何?
エラトステネスの篩(ふるい)は、指定された範囲内にある素数をすべて見つけ出すためのアルゴリズムです。
今から約2200年以上前、紀元前3世紀の古代ギリシャの数学者エラトステネスが考案したとされる方法で、現代でもプログラミングや数学の分野で広く使われています。
「篩(ふるい)」という名前の通り、数字を順番に「ふるいにかける」ように、素数ではない数(合成数)を取り除いていくことで、素数だけを残すというシンプルで賢い方法なんです。
そもそも素数って何だっけ?
エラトステネスの篩を理解する前に、素数について簡単におさらいしましょう。
素数とは、1とその数自身以外に約数を持たない2以上の整数のことです。
例えば:
- 2 → 約数は1と2だけなので素数
- 3 → 約数は1と3だけなので素数
- 4 → 約数は1、2、4なので素数ではない(合成数)
- 5 → 約数は1と5だけなので素数
- 6 → 約数は1、2、3、6なので素数ではない(合成数)
ちなみに1は素数ではありません。素数の定義は「2つの約数を持つ数」なので、1は除外されます。
エラトステネスの篩の基本的な仕組み
エラトステネスの篩は、以下のような手順で素数を見つけていきます。
基本的な考え方:
素数の倍数は必ず合成数(素数ではない数)になるという性質を利用して、倍数を次々に消していきます。最後まで消されずに残った数が素数というわけです。
実際にやってみよう!【1から100までの素数を探す】
では、1から100までの数の中から素数を見つけてみましょう。
ステップ1: 数字を並べる
まず、2から100までの数字を表にして並べます。
(1は素数ではないので最初から除外します)
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
...
91 92 93 94 95 96 97 98 99 100ステップ2: 2の倍数を消す
最初の素数は2です。2に○をつけて、2より大きい2の倍数(4, 6, 8, 10…)をすべて消します。
これで、4、6、8、10、12…という2で割り切れる数がすべて消えました。
ステップ3: 3の倍数を消す
次に残っている数の中で最小の数は3です。3に○をつけて、3より大きい3の倍数(9, 15, 21…)をすべて消します。
6や12はすでに2の倍数として消されているので、ここでは9、15、21…が新たに消えます。
ステップ4: 5の倍数を消す
次に残っている数の中で最小の数は5です。5に○をつけて、5より大きい5の倍数(25, 35, 55…)をすべて消します。
10、15、20…などはすでに消されているので、25、35、55…が新たに消えます。
ステップ5: 7の倍数を消す
次に残っている数の中で最小の数は7です。7に○をつけて、7より大きい7の倍数(49, 77, 91)をすべて消します。
ステップ6: 終了判定
ここで重要なポイントがあります。
√100 = 10 なので、10以下の素数(2, 3, 5, 7)で篩い落とす作業を終えれば、それより大きい素数の倍数はすでにすべて消されているんです。
なぜなら、100以下の合成数は必ず10以下の素因数を少なくとも1つ持つからです。
結果: 素数が見つかった!
消されずに残った数が、1から100までの素数です:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
全部で25個の素数が見つかりました!
なぜ√nまでで終わりなの?
「100までの素数を探すのに、なぜ10(√100)までの素数で篩えば十分なの?」と疑問に思った人もいるでしょう。
これには数学的な理由があります。
ある数Nが合成数(素数ではない数)だとすると、Nは2つ以上の素因数の積で表せます。
例えば、36 = 6 × 6 のように。
このとき、少なくとも1つの素因数は√N以下になります。
36の場合:
- 36 = 2 × 18 → 2は√36(=6)以下
- 36 = 3 × 12 → 3は√36以下
- 36 = 4 × 9 → 4は√36以下
- 36 = 6 × 6 → 6は√36と等しい
つまり、√100 = 10 までの素数(2, 3, 5, 7)で倍数を消せば、それより大きい合成数もすべて消されるというわけです。
エラトステネスの篩のメリット
1. シンプルで分かりやすい
複雑な計算をせずに、ただ倍数を消していくだけなので、小学生でも理解できる方法です。
2. 効率的
コンピュータで素数を探す場合、エラトステネスの篩は非常に効率的なアルゴリズムとして知られています。
計算量はO(n log log n)という、素数探索アルゴリズムの中でもかなり高速な部類に入ります。
3. 確実にすべての素数が見つかる
漏れなく、指定した範囲内のすべての素数を見つけることができます。
エラトステネスの篩の実用例
エラトステネスの篩は、古代の方法でありながら現代でも様々な場面で活用されています。
プログラミング
競技プログラミングやアルゴリズムの学習で、素数を効率的に列挙する必要がある場合によく使われます。
Python、Java、C++など、あらゆるプログラミング言語で実装できます。
暗号理論
現代の暗号技術(RSA暗号など)では、大きな素数が重要な役割を果たします。エラトステネスの篩の考え方は、こうした分野の基礎となっています。
数学研究
素数の分布や性質を研究する際に、実際に素数を列挙する必要がある場合に使われます。
エラトステネスの篩の応用と発展
エラトステネスの篩には、いくつかの改良版や応用技術があります。
線形篩
より高速な「線形篩」というアルゴリズムもあり、各数を一度しか篩わないため、さらに効率的に素数を見つけることができます。
区間篩
非常に大きな数の範囲で素数を探す場合、メモリを節約するために範囲を分割して処理する「区間篩(セグメント篩)」という技術が使われます。
アトキンの篩
2004年に発表された、エラトステネスの篩よりも理論的に高速なアルゴリズムです。
まとめ
エラトステネスの篩は、2200年以上前に考案された素数を見つけるための方法です。
重要なポイント:
- 素数の倍数を順番に消していくことで、素数だけを残す
- √nまでの素数で篩えば十分
- シンプルで分かりやすく、効率的
- 現代のプログラミングや暗号技術でも活用されている
古代ギリシャの知恵が、現代のコンピュータサイエンスにも通用しているというのは、数学の普遍性を感じさせますね。
素数に興味を持ったら、実際に紙とペンを使って1から100までの素数を探してみてください。エラトステネスの篩の巧妙さを実感できるはずです!
コメント