「次の数が素数であるかを判定せよ。素数でなかった場合は素因数分解を行うこと。
(1)$191$
(2)$259$
(3)$101$」
(1)$191$
素数判定をするには、判定したい自然数の正の平方根以下の素数を約数にもつかを調べます。
$191$の正の平方根$\sqrt{191}$はおよそ$13.8$なので、$\sqrt{191}$以下の素数は$2,3,5,7,11,13$となります。
$191$が上記の素数のどれを約数にもつかを調べてみるとどれも約数にもちません。
したがって、$191$は素数であることがわかります。
したがって、$191$は素数であることがわかります。
自然数$n$が素数であるかは正の平方根$\sqrt{n}$以下の素数を約数にもつかで判定できるのですが、$\sqrt{n}$以下の素数というのは$\sqrt{n}$の整数部分以下の素数と言い換えることができます。
ここで、$\sqrt{n}$の整数部分を$a$とおき2乗すると$a^2$は平方数となります。
すなわち、この素数判定法は調べる素数の範囲を「自然数$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$より先に約数としてもつことを見つけるはずだからです。）
（実は、$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$は素数であることがわかります。
Share:
