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

作者：知新_RL | 2024-03-27 18:53:21

踩

平方概判断质数

设被除数为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 是否为质数只需除到开平方根。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/326316?site