欧拉筛+埃式筛求素数

参考：https://blog.csdn.net/nk_test/article/details/46242401

先看一下经典的埃拉特斯特尼筛法：

 1 int prime[MAXN],vis[MAXN];
 2 void Prime(int n)
 3 {
 4     int cnt=0;
 5     memset(vis,1,sizeof(prime));
 6     vis[0]=vis[1]=0;
 7     for(int i=2;i<n;i++)
 8     {
 9         if(vis[i])
10         {
11            prime[cnt++]=i;//保存素数 
12            for(int j=i*i;j<n;j+=i)//i*i开始进行了稍微的优化
13            vis[j]=0;//不是素数 
14         }
15     }
16     return ;
17 }

时间复杂度为O(nloglogn)，原理很简单，一个素数的倍数一定是合数，删除即可。从i×i开始而不从2×i开始是因为2×i早被2的倍数筛选过了。但埃式筛法的缺点是有些数会被重复筛选，比如30会被2×15和5×6筛选。

下面介绍欧拉筛，首先我们知道任何数都能被一些素数的乘积表示，假设我们令每个合数只被它的最小素因数筛去，那么就是线性时间，算法复杂度降到了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,1,sizeof(vis));
 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]]=0;
15             if(i%prime[j]==0)//关键 
16             break;
17         }
18     }
19     return cnt;//返回小于n的素数的个数 
20 }

代码中体现在：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*prime[j-1]的最小素因子只能是prime[j-1]，因为i的最小素因子是prime[j]，而prime[j]>prime[j-1],所以在满足i%prime[j]==0这个条件之前以及第一次满足该条件时,prime[j]必定是prime[j]*i的最小因子。证毕。

但是只是求素数的话欧拉筛有些没必要，除非数据很大会卡埃式筛，欧拉筛的很重要的应用是欧拉函数.