素数判定と前後の素数の求め方

素数とは、2 以上の整数のうち、1 と自分自身以外の数では割り切れないもののことです。2, 3, 5, 7, 11 と続きます。ある数が素数かどうかを確かめる素直な方法は、小さい数から順に割ってみて、割り切れるものがあるかどうかを見ることです。これを試し割りといいます。

この計算機は、割り切れた数のうちいちばん小さいものを最小の素因数として返します。それが n 自身と同じなら、n は 1 と自分自身でしか割れなかったということですから、n は素数です。n より小さい数が出たときは、その数が n を割り切るという証拠になり、n は素数ではありません。

どこまで割れば足りるか

2 から n − 1 まで全部試す必要はありません。n が 1 以外の約数を持つとして、n = a × b と分解し、a のほうを小さいか等しいものとします。すると a × a は a × b 以下、つまり n 以下になります。

ですから、n に約数があるなら、そのうち小さいほうは必ず $\sqrt{n}$ 以下に見つかります。逆にいえば、$\sqrt{n}$ まで試して 1 つも割り切れなければ、その先を調べても無駄です。n が 10000 でも 100 まで、n が 1000000 でも 1000 までで済みます。調べる回数がぐっと減ります。

例

既定の入力 n = 91 で追ってみます。$\sqrt{91}$ は約 9.5 なので、9 まで試せば足ります。

1. 2 で割れるか。91 は奇数なので割り切れません
2. 3 で割れるか。各桁の和が 9 + 1 = 10 で 3 の倍数ではないので割り切れません
3. 5 で割れるか。一の位が 1 なので割り切れません
4. 7 で割れるか。91 ÷ 7 = 13 なので割り切れます

ここで手が止まります。最小の素因数は 7 で、91 = 7 × 13 です。91 自身ではないので、91 は素数ではありません。前後の素数は 89 と 97 で、そのあいだに素数はありません。

91 は素数に見えやすい数です。偶数でもなく、3 でも 5 でも割れないので、そこであきらめると素数だと思ってしまいます。7 まで試してはじめて正体が分かります。

気をつけること

1 は素数ではありません。素数の定義は 2 以上の整数から始まります。1 を素数に入れると、6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 のように素因数分解の書き方がいくらでも増えてしまい、答えが 1 通りに決まらなくなるためです。

2 は素数のうちでただ 1 つの偶数で、同時にいちばん小さい素数です。そのため n = 2 を入れると、直前の素数の欄にはハイフンが出ます。2 より小さい素数は存在しない、という意味です。

素数の間隔は一定ではありません。89 と 97 のように 8 も空くことがあれば、11 と 13 のように 2 しか空かないこともあります。大きい数のほうへ行くほど素数はまばらになりますが、どこまで行っても尽きることはありません。