数学Ⅰ : 数と式 素数を探す

例題

30以下の素数をすべて求めなさい。

アドバイス

例えば2015年本試 ⅠA 第2問[1]のように、センター試験を解いていると素数のリストが必要なことがある。
大きな数までは必要ないので単に素数を憶えてもらってもいいんだけど、エラトステネスのふるいという、簡単な作業でリストをつくる方法もある。
このページでは、その方法を説明する。

エラトステネスのふるい

ステップ1

例題では30以下の素数を問われている。
1は素数じゃないので、2から30までの数字を全部書く。(表A)

表A
素数を探す 解説図

例えば11以上30未満の素数を問われた場合でも、表は必ず2から始める
なので、表Bのようなものを作ってはいけない

表B
$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$
$21$$22$$23$$24$$25$$26$$27$$28$$29$$30$

以下、表Aを使って作業をする。

ステップ2

表Aの中で一番小さな数である2に○をつけて、その倍数全部(1倍は除く)に×をつける。
実際の作業手順は下のボタンを押して確認してもらいたい。

表Aのオレンジの部分が、ステップ2で行った作業だ。

ステップ3

表Aの中で○も×もついていない一番小さな数は3。この3に○をつけて、その倍数全部(1倍は除く)に×をつける。
実際の作業手順は下のボタンを押して確認してもらいたい。

表Aの緑の部分が、ステップ3で行った作業だ。

以下、同様の作業を、数の範囲の最大値の平方根まで繰りかえす。

今回は$30$以下の素数を求めるから、範囲の最大値は$30$だ。
$5\lt\sqrt{30}\lt6$
なので、ここでは5の倍数までに印をつける。

最大値の平方根が整数になる場合は、その数もチェックする。
例えば$25$以下の素数を問われた場合は、$\sqrt{25}=5$なので、5の倍数もチェックしないといけない。
もちろん、その数に×がついていたときにはチェックする必要はない。

ステップ4

次は5に○をつけて、その倍数全部(1倍は除く)に×をつける。
作業手順は下のボタン。

表Aの赤い部分が、ステップ3で行った作業だ。

次に○も×もついていない最小の数は7だけど、7は$\sqrt{30}$より大きい数なので、作業は終了。

答え

表の中で○も×もついていない数に、全部○をつける。

丸がついている数が素数だ。

解答2,3,5,7,11,13,17,19,23,29