了解筛素数之前需要了解一下素数判定的原理
素数的判定可以根据素数的定义出发：素数是其因子只有1和本身的数，即对于\(i\)属于\(2\)~\(p-1\), \(i|p\)不成立
原理为 对于每个数，它的倍数一定不是质数，我们可以划去。
bool st[N];
void select_primes(int n){
for(int i=2;i<=n;i++){
for(int j=i+i;j<=n;j+=i)
st[j]=true;
}
}
这里有一个需要注意的地方。我们从\(2\)开始遍历，遍历到某一个数时，如果它没有被筛过，那么它一定是素数。
这一点可以从素数定义出发，我们筛素数的依据还是根据数能不能分解成两个不是\(1\)的因数。对于一个数\(x\),如果遍历到它时没有被筛去，说明对于\(i\)属于\(2\)~\(n-1\)，没有一个\(i\)可以整除\(x\)，因此它就是质数。
朴素筛的时间复杂度是\(O(NlogN)\)准确的说是\(NlnN\)。可以从调和级数证明。
朴素筛做了许多重复工作。对于一个数可能会被筛多次，如8会被2和4同时筛一遍，埃氏筛就降低了重复工作。
原理为 只用质数去筛后面的数
bool st[N];
void select_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){/*未被筛过，即i为素数*/
for(int j=i+i;j<=n;j+=i)
st[i]=true;
}
}
}
发现埃氏筛和朴素筛的不同在于，只有\(i\)为素数时才开始筛它的倍数。这样做并不会使某一个数没有被筛去，因为我们有唯一分解定理。
每个大于1的自然数均可写为若干质数的积(或者说是若干质数的幂 的积)，而且这些素因子按大小排列之后，写法仅有一种方式。
所以每个合数必定可以分解成素数积的形式，必定会被筛去。
质数定理:\(1\)~\(N\)中，有\((N/lnN)\)个质数。
结合质数定理和朴素筛的复杂度判断，可得埃氏筛的时间复杂度为\(O(NloglogN)\)
但是，埃氏筛仍然做了许多重复工作。多个素数可能重复筛去同一个合数,于是有了欧拉筛。
欧拉筛又名线性筛,因为它的时间复杂度为\(O(N)\)
欧拉筛:
原理 如果想达到线性，需要满足两个条件：\(1\)，每个数只被筛一次。\(2\)，每个数都会被筛到。
欧拉筛通过维护素数表，让每个数都只被它的最小质因子筛去。
先放代码
int primes[N],cnt;
bool st[N];
void select_primes(int n){
for(int i=2;i<=n;i++){
if(!st[i])/*未被筛过,说明是素数*/
primes[cnt++]=i;/*加入素数表*/
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;/*用素数表筛后面的元素*/
if(i%primes[j]==0)
break;
}
}
}
分析代码,内层循环是利用素数表去筛素数。当\(primes[j]\)可以整除i时，就应该退出，这样确保了每一个数只被最小质因子筛了一次。具体原理为:对一个被筛的数x 可以表示为\(x=primes[j]*i\)
如果\(primes[j]\)不能整除\(i\)，则有\(i\)的最小质因子\({k>primes[i]}\) (素数表从小到大遍历)，
且因为\({k>primes[j]}\),则\(x\)不包含比\(primes[j]\)更小的质因子。
此外还有是否会被重复筛，如果\(x\)还存在比\(primes[j]\)大的质因子,则\(x\)可以写作\(x=primes[j+idx] * (i-var)\)（\(j+idx\)表示，比\(j\)大的某个数，\(i-var\)表示比\(i\)小的某个数值）
但是我们的\(i\)是从小到大枚举的，x被筛过之后不可能出现\(i-var\)的情况。
还需要使得每个合数都被筛掉，对于一个合数\(x\),\(x\)被筛时一定是\(x=primes[j] * i\)，遍历\(x\)之前一定遍历过了\(i\)，则\(x\)一定会通过\(i\)被筛掉。
关于欧拉筛的复杂度：看上去欧拉筛的内层循环会执行多次。当\(i\)很小，\(i\)要去筛很多数，看上去比较费时。但当\(i\)比较大时，内层循环几乎不用去执行。对于每个\(i\)均摊后仍是线性的。
原文：https://www.cnblogs.com/yaohui-zhang/p/14638728.html