您的位置: 首页  >  文章  >  [算法]素数筛法

[算法]素数筛法

分类: 文章 • 2025-01-18 17:32:52

【方法一】

[算法]素数筛法

[算法]素数筛法

【代码一】

[cpp]view plaincopy
  1. //判断是否是一个素数
  2. intIsPrime(inta){
  3. //0,1，负数都是非素数
  4. if(a<=1){
  5. return0;
  6. }
  7. //计算枚举上界，为防止double值带来的精度损失，所以采用根号值取整后再加1，即宁愿多枚举一个，也不愿少枚举一个数
  8. intbound=(int)sqrt(a)+1;
  9. for(inti=2;i<bound;i++){
  10. //依次枚举这些数能否整除x，若能则必不是素数
  11. if(a%i==0){
  12. return0;
  13. }
  14. }
  15. return1;
  16. }

[算法]素数筛法

【方法二】

[算法]素数筛法

【代码二】

[cpp]view plaincopy
  1. #defineMAXSIZE10001
  3. intMark[MAXSIZE];
  4. intprime[MAXSIZE];
  6. //判断是否是一个素数Mark标记数组index素数个数
  7. intPrime(){
  8. intindex=0;
  9. memset(Mark,0,sizeof(Mark));
  10. for(inti=0;i<MAXSIZE;i++){
  11. //已被标记
  12. if(Mark[i]==1){
  13. continue;
  14. }
  15. else{
  16. //否则得到一个素数
  17. prime[index++]=i;
  18. //标记该素数的倍数为非素数
  19. for(intj=i*i;j<MAXSIZE;j+=i){
  20. Mark[j]=1;
  21. }
  22. }
  23. }
  24. returnindex;
  25. }

【方法三】

这种方法比较好理解，初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数

把这些合数都筛掉，即算法名字的由来。但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。

比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。所以，也就有了快速线性筛法。

【代码三】

[cpp]view plaincopy
  1. intMark[MAXSIZE];
  2. intprime[MAXSIZE];
  4. //判断是否是一个素数Mark标记数组index素数个数
  5. intPrime(){
  6. intindex=0;
  7. memset(Mark,0,sizeof(Mark));
  8. for(inti=2;i<MAXSIZE;i++)
  9. {
  10. //如果未标记则得到一个素数
  11. if(Mark[i]==0){
  12. prime[index++]=i;
  13. }
  14. //标记目前得到的素数的i倍为非素数
  15. for(intj=0;j<index&&prime[j]*i<MAXSIZE;j++)
  16. {
  17. Mark[i*prime[j]]=1;
  18. if(i%prime[j]==0){
  19. break;
  20. }
  21. }
  22. }
  23. returnindex;
  24. }
利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。
代码中体现在：
if(i%prime[j]==0)break;
prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛掉。
因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。

在满足i%prme[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。





参考博文：点击打开链接


习题练习：点击打开链接







相关推荐