ある数が素数かどうかをテストするには、なぜその数がその数の平方根までしか割り切れないかどうかをテストする必要があるのでしょうか?
ベストアンサー1
数が素数でない場合は、n2 つの因数に分解できますa。b
n = a * b
ここでa、 と がb両方とも の平方根より大きくなることはできませんn。その場合、積がa * bより大きくなるからですsqrt(n) * sqrt(n) = n。したがって、 の因数分解ではn、少なくとも 1 つの因数が の平方根以下でなければならず、n平方根以下の因数が見つからない場合は はn素数でなければなりません。