Question

素数判断问题:为什么从2开始到该整数的平方根

网上有很多判断素数的编程题，算法中为什么要从2开始到该整数的平方根，从2开始到该整数-1这个范围很容易理解。有哪位朋友能解释一下这个问题，非常感谢！

Answer 1

判断一个数是否素数，只需判断它是否有非1，非本身的正因子。
一般算法都是从2开始判断，设该数是N，假如N有大于 根号N 的因子，那么它的另一个因子必小于 根号N，那么计算机运算时查到这个因子时就可判断它不是素数，因此只需到平方根，而不必查到 N-1

Answer 2

因为如果整数m有一个比它的平方根m^(1/2)还要大的因数的话，即m=k1*k2,其中，k1>=m^(1/2)+1,则其另一个因数k2<=m^(1/2).因此，整数m的因数（如果有的话）只需考察到m的平方根即可。

Answer 3

对任意合数n，根据定义可以设n=pq(p<=q)则p<=根号n
从而若n>1且不是素数，则它的最小素因子一定不超过p,从而不超过根号n。
由此得上面的算法，即只需要检验正整数的最小素因子即可。
希望对你有所帮助！