エラトステネスのふるい２
なぜ7の倍数を消すところまでやれば、100までの素数がすべてわかるのか。この理由は、エラトステネスのふるいを自分の手で実行してみるとよくわかる。下に数の並びを再び用意したので、今度は手順に従って、自分の手で倍数を消してみよう。数をクリックするとその数が消え、もう一度クリックすると赤枠で囲まれるようにしてある。念のため、答え合わせボタンも用意しておいたので、自分で消した後にクリックしてみよう。
- 1は素数ではないので1を消す。
- 2は素数なので赤で囲み、続く2の倍数を消す。
- 3は素数なので赤で囲み 続く3の倍数を消す。
- 5は素数なので赤で囲み、続く5の倍数を消す。
- 7は素数なので赤で囲み 続く7の倍数を消す。
倍数を消そうとしたときに、すでに消されているものがあるのに気付いただろうか。3の倍数を消そうとしたときには、すでに6は消えていたはず。5の倍数を消そうとしたときには、すでに10や15、20は消えていたはずだ。なぜそうなる？ この理由がわかれば、7の倍数まで消せば100以下の素数がすべてわかる理由にぐっと近づける。