筛法求素数

线性筛法求素数:

基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。

cnt=0;
void make_prime()  {      
    memset(prime, 1, sizeof(prime));
    prime[0]=false;     
    prime[1]=false;     
    int N=31700;      
    for (int i=2;  i<N;  i++)         
      if (prime[i]) {          
        primes[++cnt ]=i;     
        for (int k=i*i; k<N; k+=i)        
            prime[k]=false;       
      }      
    return;
}   

此方法效率不高：比如10，在i=2的时候，k=2*15筛了一次；在i=5，k=5*6 的时候又筛了一次。

快速线性筛法：

#include<iostream>
using namespace std;    
const long N = 200000;   
long prime[N] = {0},num_prime = 0;    
int isNotPrime[N] = {1, 1};   
int main()    
{     
         for(long i = 2 ; i < N ; i ++)       
           {            
        if(! isNotPrime[i])               
             prime[num_prime ++]=i;  
        //关键处1        
        for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)
            {               
                  isNotPrime[i * prime[j]] = 1;  
              if( !(i % prime[j] ) )  //关键处2                  
                break;           
        }        
    }        
    return 0;   
}  

首先，先明确一个条件，任何合数都能表示成一系列素数的积。

不管 i 是否是素数，都会执行到“关键处1”，

①如果 i 都是是素数的话，那简单，一个大的素数 i 乘以不大于 i 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 N=p1*p2的形式, p1，p2之间不相等

②如果 i 是合数，此时 i 可以表示成递增素数相乘 i=p1*p2*...*pn, pi都是素数（2<=i<=n），  pi<=pj  ( i<=j )

p1是最小的系数。

根据“关键处2”的定义，当p1==prime[j] 的时候，筛除就终止了，也就是说，只能筛出不大于p1的质数*i。

我们可以直观地举个例子。i=2*3*5

此时能筛除 2*i ,不能筛除 3*i

如果能筛除3*i 的话，当 i' 等于 i'=3*3*5 时，筛除2*i' 就和前面重复了。

第一种的优化：直接把偶数去掉再筛选；

我推荐这个算法！ 易于理解。 只算奇数部分，时空效率都还不错！
half=SIZE/2; 
int sn = (int) sqrt(SIZE); 
for (i = 0; i < half; i++) 
   p[i] = true;// 初始化全部奇数为素数。p[0]对应3，即p[i]对应2*i+3 
for (i = 0; i < sn; i++) {    
if(p[i])//如果 i+i+3 是素数
{     
    for(k=i+i+3, j=k*i+k+i; j < half; j+=k) 
    // 筛法起点是 p[i]所对应素数的平方 k^2                                        
    // k^2在 p 中的位置是 k*i+k+i
    //    下标 i         k*i+k+i
    //对应数值 k=i+i+3   k^2         
       p[j]=false; 
} 
} 
//素数都存放在 p 数组中，p[i]=true代表 i+i+2 是素数。
//举例，3是素数，按3*3,3*5,3*7...的次序筛选，因为只保存奇数，所以不用删3*4，3*6....

 根号法：如果一个数X不能被 [2, 根号X ] 内的所有数整除，那么它就是素数

void prime(void)    //素数组打表  
{  
  
    int tally=2;  
    int i,j,flag;  
    for(i=5;i<10000;i+=2)  
    {  
        for(j=0,flag=1;prim[j]*prim[j]<=i;j++)  
            if(i%prim[j]==0){flag=0;break;}  
        if(flag)  
        {  
            prim[tally]=i;  
            tally++;  
        }  
    }  
    return;  
}