要测试一个数字是否为质数,为什么我们必须测试该数字是否只能被该数的平方根整除?
如果数字n
不是素,它可以分解成两个因素a
和b
:
n = a * b
现在a
并且b
不能都大于的平方根n
,因为从那以后乘积a * b
将大于sqrt(n) * sqrt(n) = n
。因此,在的任何因式分解中n
,至少一个因数必须小于的平方根n
,并且如果我们找不到任何小于或等于平方根的因数,则n
必须为素数。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句