[解決済み] 素数かどうかを判断するのに、なぜ平方根まで確認するのか？

疑問点

ある数が素数かどうかを調べるのに、なぜその数の平方根までしか割り切れないかどうかを調べなければならないのでしょうか？

どのように解決するのですか？

もし、ある数字が n が素数でない場合、2つの因数に分解することができます。 a と b :

n = a * b

現在 a と b の平方根より大きいことはありえない。 n となり、その積は a * b よりも大きくなる。 sqrt(n) * sqrt(n) = n . ということは、どのような因数分解でも n の平方根より小さくなければならない。 n で、平方根以下の因子が見つからなければ n は素数でなければならない。