高校问答精工钢结构:判断一个数m为素数时，为什么只要将它从1除到根号m即可？
来源：百度文库 编辑：高校问答 时间：2024/05/03 04:55:15
能给出证明吗？
因为若m不整除从1除到根号m的数它就不可能整除根号m后面的数.
因为若m整除n(其中n>根号m)则m=n*k,而因为n>根号m,所以k<根号m,有矛盾(与m不整除从1除到根号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其实已经和前面对应了不过就是顺序反了而这个临界点就是开方的那个数