素数判定と素因数分解 例題

「次の数が素数であるかを判定せよ。素数でなかった場合は素因数分解をおこなうこと。

(1)$191$

(2)$259$

(3)$101$」

(1)$191$

　素数判定をするには、判定したい自然数の正の平方根以下の素数を約数にもつかを調べます。

$191$の正の平方根$\sqrt{191}$はおよそ$13.8$なので、$\sqrt{191}$以下の素数は$2,3,5,7,11,13$となります。

$191$が上記の素数のどれを約数にもつかを調べてみるとどれも約数にもちません。
したがって、$191$は素数であることがわかります。

　自然数$n$が素数であるかは正の平方根$\sqrt{n}$以下の素数を約数にもつかで判定できるのですが、$\sqrt{n}$以下の素数から$\sqrt{n}$の整数部分以下の素数と範囲を狭めても問題ありません。

ところで、$\sqrt{n}$の整数部分を$a$とおくと、これの2乗$a^2$は平方数となります。
$\sqrt{n}$の整数部分$a$は$\sqrt{n}$以下の最大の整数なので、$a^2$は$n$以下の最大の平方数となります。

したがって、この素数判定法の調べる素数の範囲を「自然数$n$以下の最大の平方数$a^2$の正の平方根$a$以下の素数」のように定めてもよいということになります。

$(1)$を例にしてこの方法をもちいてみると

$191$以下の最大の平方数は$13^2=169$なので、$13$以下の素数を約数にもつかを調べるとどれも約数にもちません。

したがって、$191$は素数であることがわかります。

(2)$259$

　$259$以下の最大の平方数は$15^2=225$なので、$15$以下の素数を約数にもつか調べます。

$15$以下の素数は$2,3,5,7,11,13$です。この中で$259$の約数となるのは$7$で、$259$は

$$259=7\times37$$

と書けます。

$37$を素数判定すると、$6^2=36$より$6$以下の素数$2,3,5$のいずれも約数にもたないので素数であることがわかります。
（実は、$259$が$15$以下の素数を約数としてもつかを小さい順に調べていたなら$37$の素数判定のために調べる必要のある素数がわかった時点で$37$が素数であると判定できます。素数$2,3,5$が$37$のいずれかを約数としてもつならそれは$259$との公約数でもあるので、$7$より先に約数としてもつことを見つけるはずだからです。）

したがって、

$$\large259=7\times37$$

が解答となります。

(3)$101$

　$101$以下の最大の平方数は$10^2=100$なので、$10$以下の素数を約数にもつか調べます。

$10$以下の素数は$2,3,5,7$です。ここで、互いに素であることを利用して素数の候補を絞り込む方法を紹介します。

$100$と$101$は隣り合う整数なので互いに素です。すなわち、$101$は$100$の素因数$2,5$のいずれも約数にもたないということです。

関連：互いに素とは？

したがって、$10$以下の素数$2,3,5,7$のうち$3,7$を約数にもつかだけを調べればよいことがわかります。

$101$は$3,7$のいずれも約数にもたないので、$101$は素数であることがわかります。

関連：なぜ素数であるかを平方根以下の素数を約数にもつかで判定できるのか？