エラトステネスのふるい３
もう一度、自分の手で倍数を消してみよう。2の倍数や3の倍数は数が多く大変なので、下のリストではすでに消してある。5の倍数からスタートだ。ただし今度は、
- \( 5\times 2 \) → 消えてる
- \( 5\times 3 \) → 消えてる
- ……
- \( 5\times\)□ → まだ消えてない！
というように小さな倍数から始めて、最初に消さなければならない\(5 \times\)□ を見つけてみてほしい。続いて5の倍数を全部消したら、今度は7の倍数を消すときにも、同じことを調べてみよう。
消さなければならない最初の掛け算は見つかっただろうか。下に答えを書いておいたので、マスクをクリックして答え合わせをしてみてほしい。
5の倍数で最初に消さなければならないのは \(5 \times 5\)
7の倍数で最初に消さなければならないのは \(7 \times 7\)
理由を確認しておこう。まずは5の倍数から。
\(5 \times 2 \) \(2\) の倍数を消すときに消える。
\(5 \times 3 \) \(3\) の倍数を消すときに消える。
\(5 \times 4 \) \(2\) の倍数を消すときに消える。
というわけで、 \(5\times 5\) が消さなければならない最初のものとして残っていたわけだ。
7の倍数についても同様に、
\(7 \times 2 \) \(2\) の倍数を消すときに消える。
\(7 \times 3 \) \(3\) の倍数を消すときに消える。
\(7 \times 4 \) \(2\) の倍数を消すときに消える。
\(7 \times 5 \) \(5\) の倍数を消すときに消える。
\(7 \times 6 \) \(2\) の倍数を消すときに消える。
というわけで、 \(7\times 7\) が消さなければならない最初のものとして残っていた、ということになる。
では、いよいよ本題だ。7の次の素数は11だが、11の倍数を消すときにも \(11\times 2\) や、\(11\times 3\) などはすでに消されている。最初に消さなければならないのはいくつだろう。
11の倍数で最初に消さなければならないのは \(11 \times 11=121\)
これより小さな11の倍数は、すでに他の数の倍数として消えてしまっているわけで、改めて消す必要はない。これが、7の倍数まで消せば100以下の素数がすべてわかる理由だ（正確には、121未満の素数でない数は、すべて消された状態になっている）。こんなに手軽で簡単な方法を考えつくなんて、エラトステネスさんってすごいね。