为什么判断 n 是否为质数只需除到开平方根就行了？（直接证明）

设被除数为n，除数为整数m；

假设 n-1 >= m >= √n；
若 n / m 不为整数，则 m 不为 n 的因数；

若 n / m 为整数，因为 m > =√n，所以有 1 < n / m <= √n；
得到 n = （ n / m ） * m；

由上式可知，当我们验证 n / m 是否整除 n 的时，也同时验证了 m 对 n 的整除性，所以只需验证 n / m 对 n 的整除性即可；

又因为 1 < n / m < =√n，所以判断 n 是否为质数只需除到开平方根。

总结

以上是生活随笔为你收集整理的为什么判断 n 是否为质数只需除到开平方根就行了？（直接证明）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。