首页 > 代码库 > [算法]素数筛法

[算法]素数筛法

2024-08-07 06:10:22   223人阅读

【方法一】


【代码一】

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


【方法二】


【代码二】

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

【方法三】

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

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

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

【代码三】

[cpp] view plaincopy
  1. int Mark[MAXSIZE];  
  2. int prime[MAXSIZE];  
  3.   
  4. //判断是否是一个素数  Mark 标记数组 index 素数个数  
  5. int Prime(){  
  6.     int index = 0;  
  7.     memset(Mark,0,sizeof(Mark));  
  8.     for(int i = 2; i < MAXSIZE; i++)  
  9.     {  
  10.         //如果未标记则得到一个素数  
  11.         if(Mark[i] == 0){  
  12.             prime[index++] = i;  
  13.         }  
  14.         //标记目前得到的素数的i倍为非素数  
  15.         for(int j = 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.     return index;  
  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的最小因子。





参考博文：点击打开链接


习题练习：点击打开链接







[算法]素数筛法


联系
我们