Question

判断是否为素数时，只除到根号数的原因是什么？

Answer 1

判断是否为素数时，只除到根号数的原因是：

因为若m整除n(其中n>根号m)则m=n*k。

因为若m不整除从1除到根号m的数它就不可能整除根号m后面的数。

如果根号m有小于SQRT(m)的因子X，那么N必定有大于SQRT(m)的因子Y与X对应。

而且X*Y=m。

所以只需要枚举1..SQRT(m)的数即可，还要考虑m为完全平方数的特殊情况。

比如：64

2*32=64 8*8=64。

如果再往后面算如32*2=64其实已经和前面对应了。

不过就是顺序反了而这个临界点就是开方的那个数。