涉及根号的质数原理解释_求素数开方的原理

作者：AllinToyou | 2024-03-27 18:55:59

踩

求素数开方的原理

对于任何的正整数N，都存在如下表达式N=x*y;（x,y不一定是正整数），我们可以假设x<=y，那么存在如下关系：

N>=x*x

所以x的取值范围是1到N的开方。也就说N的较小因子的取值范围是1到N的开方。

显然，如果N能被较小因子整除，那么我们就不用再判断能不能被较大因子整除了，例如12能被2整除，那么我们就不用再判断是否能被6整除了。

因此新的算法只要保证N在2到N的开方范围内不能被整除即可说明该数是素数。那在这种情况下用循环变量与N（终点值）比较已经不合适了，因为前者最大取到N的开方，是永远小于后者的。

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