最基本的判断质数的方法就是通过枚举所有小于这个数的数字,相除来判断是否能被整除。
代码↓
1 | if (x == 2)return true; |
在这里的循环条件的判断采用的是i <= x / i,由用sqrt的写法,但是这个太慢了。也有用i * i的写法但是如果数据范围接近于int最大时,i * i的结果就溢出了。
埃氏筛法:
基本思路是通过一个质数,找出它所有的倍数并筛去,剩下没被筛去的就是质数。
##代码↓
1 | for(int i=2;i<=n;i++) |
线性筛法
与埃氏筛法相比线性筛法对每个数字筛选一次即可达到效果,而对埃氏筛法来说,例如质数2和3,他们都会筛选到6这个数字,6就被筛了两次。对线性筛法来说,它根据以下原理:分解质因数时总是能够得到一个最小的质因数,即最小质因数乘一个最大的因数,这样所得到的数就是唯一的。每个数就只遍历了一次
1 | for (int i = 2; i <= n; i++) |
本文作者: jiangyuhao
本文链接: http://example.com/2022/02/28/%E8%B4%A8%E6%95%B0/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!