1. Eratosthenes筛法（埃氏筛）
流程：对于每一个质数\(p\)，标注出范围内所有\(p\)的倍数为合数，剩下的就是质数。
int cnt, prm[MAX], v[MAX];
void Eratosthenes()
{
for (int i = 2; i <= N; i++)
if (!v[i]) {//如果未被标记，则是质数
prm[++cnt] = i;
for (int j = 2; i * j <= N; j++)
v[i * j] = 1;//标记所有i的倍数
}
}
复杂度为\(O(nloglogn)\)
感性理解：每个质数都要在\(N\)范围内筛出所有倍数，运算量为
我们知道调和和\(1+\frac 12+ \frac 13+...+ \frac 1n\)积分估值是趋近于\(ln n\)的。同时由质数定理，\(N\)很大时，质数的密度为\(\frac 1{lnn}\)。可以近似认为平均每\(ln n\)个数中有一个质数，计第\(i\)个质数为所以“质数调和级数”约为
最后就出现了两个\(log\)。
证明：知乎上看到的转载，很复杂，关键在于证明\(\sum_{p\le n} \frac 1p\)的值。这篇文章证明了Mertens‘ theorems，即质数调和级数与\(lnlnn\)差为定值。
2. Eratosthenes的优化
- 对于合数\(n=p_1p_2...p_k\)，显然至少有一个质因子是小于\(\sqrt n\)的，于是只需要枚举到\(\sqrt n\),可以保证之后没被标记的都是质数，合数均已被标记。
- 当枚举到质数\(p\)时，\(p\)以下的质数都已经枚举过了，所以\(2p,3p,5p,...\)已经被标记，直接从\(p^2\)开始标记即可。
int cnt, prm[MAX], v[MAX];
void Eratosthenes()
{
for (int i = 2; i * i <= N; i++) // 1
if (!v[i]) {
prm[++cnt] = i;
for (int j = i; i * j <= N; j++) // 2
v[i * j] = 1;
}
}
复杂度没有变化，但是降低了常数
3. Euler筛法（欧拉筛）
埃氏筛中每个合数会被所有质因子分别筛一次。欧拉筛巧妙的设计使得每个合数只会被筛一次。
流程：从小到大枚举每一个数，将小于等于该数最小质因子的所有质数与该数相乘并标记。并记录每个数的最小质因子供下次标记。
比如说当前枚举到\(7\times11 = 77\)，其最小质因子为7，那么将\(2\times77,3\times77,5\times77,7\times77\)标记即可。
为什么这样是线性的？如果合数分解\(n = p_1p_2...p_k(p_1\le p_2 \le...)\)由于规定了“小于最小质因子的质数才会相乘标记”，\(n\)只会被\(p_1(p_2p_3...p_k)\)的组合标记一次，即每个合数都由最小质因子来标记。如上文中\(2\times77\)只会由2标记一次，而\(11*77\) 没有被标记，他的最小质因子为7，会在稍后被\(7 * 121\)标记。这样就做到的合数与标记筛除的一一对应。复杂度为\(O(n)\)
void Euler()
{
for (int i = 2; i <= N; i++) {
if (!v[i]) { //v[i]除去标记外，还记录每个数最小质因子的
v[i] = i;
prm[++cnt] = i;
}
for (int j = 1; j <= cnt; j++) {
//枚举小于等于v[i]的所有质数并标记
if (prm[j] > v[i] || prm[j] * i > N) break;
v[prm[j] * i] = i;//记录其最小质因子
}
}
}
在实际应用中欧拉要更常用，不过\(loglogn\)实在太小，而且欧拉筛常数稍大，两者的效率差距很小。