素数を見つけるためにはいくつかの方法があります。
今回はその中の１つである「エラトステネスの篩(ふるい)」について紹介します。
エラトステネスの篩とは、「素数の約数は1と自分自身の2つのみ」という性質を利用して素数を見つける方法です。今回は1~100までの数から素数を見つけましょう。
- まずは１を消す
- ２の倍数を消す
- ３の倍数を消す
- ５の倍数を消す
- ７の倍数を消す
- 残った数が１～100までの素数
まずは1を消す
最初に1を消します。
次に、2は素数ですので「〇」を書きます。一方、2の倍数は約数に必ず2が入ってしまうので素数ではありません。ですので2より大きい2の倍数を消していきます。
これで、2の倍数以外の数が残りました。
同じように3の倍数も消してみよう
消されずに残っているマスのうち、一番小さい数は3です。
同様に3の倍数も消してみると……
だんだん残っている数が少なくなってきましたね。
消されていないマスの中で一番小さい数は5になので、また同じように5の倍数も消してみます。
消されてていない数を見ると、九九表にはない数が多くなってきました。
次に7の倍数を消していきます。
7までくると、新たに消すところは3か所のみ。だいぶ少なくなりましたね。
ここまで来てでも消されず残った数が、1～100までの中にある素数となります！
実は7まで調べると、この方法では120までの素数を探し出すことができます。
（11まで調べると168まで素数を探し出すことができます）
エラトステネスの篩、あなたもやってみませんか？
エラトステネスの篩、いかがでしたでしょうか？
単に素数を丸暗記するのではなく、九九表に表して見つけ出すと視覚的にも分かりやすいですね！
やってみたいという方は、ぜひ写真で使っているシートをダウンロードして試してみてください。
