欧拉线性筛法打表素数

关于素数的判定，很多方法都太慢了，而欧拉线性筛法打表算是较快的一种，可以处理较大的数据

复杂度为O(n)

 1 const int MAXN=3000001;
 2 int prime[MAXN];//保存已经求出的素数 
 3 bool vis[MAXN];//判断是不是素数
 4 int Prime(int n)
 5 {
 6     int cnt=0;
 7     memset(vis,0,sizeof(vis)); //vis[]=0指是素数
 8     for(int i=2;i<n;i++)
 9     {
10         if(!vis[i])
11         prime[cnt++]=i;
12         for(int j=0;j<cnt&&i*prime[j]<n;j++)
13         {
14             vis[i*prime[j]]=1;
15             if(i%prime[j]==0)//欧拉筛法的精髓之处，目的是为了不重复筛除数据
16             break;
17         }
18     }
19     return cnt;//返回小于n的素数的个数 
20 }

此方法里最难理解的就是 if(i%prime[j]==0)这步判定

举个例子

prime：2,3

vis（不是素数即vis[]=1的值）：2,6,9

运行到i=4，vis内增加8，然后由于4%2==0，不进行4*3=12；

因为4是2的倍数，而在后面i=6的时候，2*6会对12进行筛除，所以此时就没必要对4*3进行计算

这样就不会造成重复筛除

再如i=15，prime到达5的时候，15%5==0，就不对之后的7,11,13等进行乘15的筛除

因为7*15=7*3*5=21*5，到i=21的时候，5再乘21进行筛除

11*15=11*3*5=33*5，到i=33时，5再乘33进行筛除