素数とは？一覧・定義・見分け方

素数とは、$1$ より大きい整数で、正の約数がちょうど2つ、つまり $1$ とその数自身だけである数のことです。したがって、$2, 3, 5,$ と $7$ は素数で、$1$ は素数ではなく、$12$ のような数は合成数です。

$1$ より大きい整数で、正の約数が2つより多いものを合成数といいます。たとえば、$12$ は $1, 2, 3, 4, 6,$ と $12$ で割り切れるので合成数です。

50までの素数

$50$ までの素数は次のとおりです。

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47$$

素数の間隔には、単純に繰り返す規則はありません。たとえば、$11$ と $13$ は近いですが、次の $23$ から $29$ までの間隔はそれより大きくなっています。

数が素数になる条件

ある数が素数であるためには、次の2つの条件を満たす必要があります。

1. $1$ より大きいこと。
2. 正の約数が $1$ とその数自身だけであること。

このため、$1$ は素数ではありません。また、$2$ は偶数ですが素数です。$2$ の正の約数は $1$ と $2$ のちょうど2つだけだからです。

ある数が素数かどうかを調べる方法

整数 $n > 1$ については、$2$ から $\lfloor \sqrt{n} \rfloor$ までの整数のどれかで余りなく割り切れるかを調べれば、素数かどうかを判定できます。

理由は実用的です。もし $n = ab$ なら、因数のどちらか一方は必ず $\sqrt{n}$ 以下になります。したがって、$\sqrt{n}$ まで調べても約数が見つからなければ、それより大きいところに新しい因数の組が隠れていることはありません。

実際には、まず簡単な割り切れ方のルールを先に確認することが多いです。

1. $n$ が偶数で、しかも $2$ より大きければ、素数ではありません。
2. 各位の数字の和が $3$ の倍数なら、$n$ は $3$ で割り切れます。
3. $n$ の一の位が $0$ または $5$ で、しかも $5$ より大きければ、$5$ で割り切れます。

これらの近道だけで素数だと証明できるわけではありませんが、多くの合成数をすばやく除外するのに役立ちます。

例題：$29$ は素数ですか？

$29$ を調べるには、まず

$$\sqrt{29} \approx 5.38$$

であることに注目します。

したがって、$5$ までの整数の約数を調べれば十分です。

• $29$ は奇数なので、$2$ では割り切れません。
• $2 + 9 = 11$ で、$11$ は $3$ の倍数ではないので、$29$ は $3$ では割り切れません。
• 一の位が $0$ または $5$ ではないので、$29$ は $5$ では割り切れません。

ここでは $4$ を調べても新しい情報はありません。$4$ の倍数はすべて偶数であり、$29$ はすでに $2$ で割り切れないと分かっているからです。

$5$ までに約数は見つからないので、$29$ は素数です。

素数でよくある間違い

$1$ を素数だと言ってしまう

それは誤りです。定義では正の約数がちょうど2つ必要ですが、$1$ の正の約数は1つしかありません。

奇数はすべて素数だと思ってしまう

奇数でも合成数はたくさんあります。たとえば、$21$ は奇数ですが、

$$21 = 3 \times 7$$

となるので、素数ではありません。

必要以上に先まで調べてしまう

素数かどうかだけを判定したいなら、$n$ より小さいすべての数を試す必要はありません。$\sqrt{n}$ まで調べれば十分です。

素数はどこで使われるのか

素数は、素因数分解、割り切れ方、最大公約数、最小公倍数の問題でよく使われます。重要なのは、$1$ より大きいすべての整数が、順序を除けば一意的に素因数の積に分解できることです。

また、素数は合同式や暗号でも登場します。暗号の分野では、より専門的な設定のもとで、大きな素数が追加の規則やアルゴリズムとともに使われます。

似た問題に挑戦してみよう

同じ平方根の方法で、$47$ と $51$ を調べてみましょう。片方は素数で、もう片方は合成数です。$\sqrt{n}$ で止めるルールが納得できるかを確かめるのにちょうどよい練習です。