エラトステネスの篩(ふるい)で100までにある素数を見つける方法

素数を見つけるためにはいくつかの方法があります。
今回はその中の1つである「エラトステネスの篩(ふるい)」について紹介します。

エラトステネスの篩とは、「素数の約数は1と自分自身の2つのみ」という性質を利用して素数を見つける方法です。今回は1~100までの数から素数を見つけましょう。

まずは1を消す

最初に1を消します。

次に、2は素数ですので「〇」を書きます。一方、2の倍数は約数に必ず2が入ってしまうので素数ではありません。ですので2より大きい2の倍数を消していきます。

これで、2の倍数以外の数が残りました。

同じように3の倍数も消してみよう

消されずに残っているマスのうち、一番小さい数は3です。
同様に3の倍数も消してみると……

だんだん残っている数が少なくなってきましたね。
消されていないマスの中で一番小さい数は5になので、また同じように5の倍数も消してみます。

消されてていない数を見ると、九九表にはない数が多くなってきました。

次に7の倍数を消していきます。

7までくると、新たに消すところは3か所のみ。だいぶ少なくなりましたね。

ここまで来てれでも消されず残った数が、1~00までの中にある素数となります!

実は7まで調べると、この方法では120までの素数を探し出すことができます。

(11まで調べると168まで素数を探し出すことができます)

エラトステネスの篩、あなたもやってみませんか?

Nordisk familjebok, Public domain, ウィキメディア・コモンズ経由で

エラトステネスの篩、いかがでしたでしょうか?

単に素数を丸暗記するのではなく、九九表に表して見つけ出すと視覚的にも分かりやすいですね!

やってみたいという方は、ぜひ写真で使っているシートをダウンロードして試してみてください。

≫≫素数探しシート(PDFファイル)

よかったらシェアしてね!