素因数分解

戻る


中学では平方根の中は最小の自然数にするように求められます。
その際は素因数分解を使うので、その方法を知らないと出来ません。
小さい数の素因数分解は、その数までの素数で確認すれば良いのですが、大きい数の素因数分解 は途中で打ち切りにしないと、極めて大変です。
つまり、素数の約数が見つからない場合に、いつ打ち切るかの問題です。


899を素因数分解する

小さい方の素数から順に2,3,5,7,11,13,17,19 を使い、それで899を割ると、 いつまでたっても割り切れません。そこで、どこまで試して割り切れなかったら 止めるかの話になります。
素数の二乗が899を越えたら止めてよいです。
29は841、31は961なので、
2,3,5,7,11,13,17,19,23,29までためして割り切れる素数が無ければそれでやめて構いません
ちなみに 899=29x31 です。