筛法

求所有不大于 $n$ 的质数 容易想到对所有不大于 $n$ 的正整数逐个判断是不是质数，但这不是好主意。

调和级数

设调和级数前 $n$ 项的和为 $f(n)$，即 $f(n) = \sum_{i=1}^{n} \frac{1}{i}$

可以证明 $f(n)=O(logn)$

筛法一：朴素筛法

从 $2$ 到 $n$ 枚举整数 $i$，标记大于 $i$ 且不大于 $n$ 的 $i$ 的倍数。枚举到 $i$ 时，若 $i$ 没有被标记过，则 $i$ 为质数。 复杂度为 $O(\sum_{i=1}^{n} \frac{n}{i})=O(nlogn)$

bool vis[N + 1];
vector<int> p;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) p.push_back(i);
        for (int j = i * 2; j <= N; j += i) 
            vis[j] = 1;
    }
}

筛法二：埃氏筛法（埃拉托斯特尼筛法）

从 $2$ 到 $n$ 枚举整数 $i$，若 $i$ 是质数，标记大于 $i$ 且不大于 $n$ 的 $i$ 的倍数。枚举到 $i$ 时，若 $i$ 没有被标记过，则 $i$ 为质数。

可以证明复杂度为 $O(\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} ...) = O(nloglogn)$。这种筛法有个不好记的名字。

bool vis[N + 1];
vector<int> p;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) {
            p.push_back(i);
            for (int j = i * 2; j <= N; j += i) 
            vis[j] = 1;
        }
    }
}

筛法三：欧拉筛法（线性筛法）

从 $2$ 到 $n$ 枚举整数 $i$，再从小到大枚举所有不大于 $i$ 的最小质因子 $p_0$，标记为 $i*p_0$。显然，枚举到的 $p_0$ 总是 $i*p_0$ 的最小质因子，而更大的 $p_0$ 均不可能是 $i*p_0$ 的最小质因子。同样，枚举到 $i$ 时，若 $i$ 没有被标记过，则 $i$ 为质数。

每个合数都只会在其最小的质因子被枚举时被标记，故复杂度为 $O(n)$，这种筛法称为欧拉筛或线性筛。

bool vis[N + 1];
vector<int> p;
void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!vis[i]) p.push_back(i);
        for (int j = 0; i * p[j] <= N; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

重点理解这句话： if( i % prime[j] == 0 ) break;

问题：

1、怎么证明prim[j]就是 i*prime[j]的最小质因子？

分情况讨论： 假如 i%prime[j] == 0 ，那么prime[j]一定是i的最小质数，因为prime[j]是从小到大枚举的，所以它也是 i*prime[j] 的最小质因子。

假如 i%prime[j] ！= 0 ，那么prime[j] 一定小于 i 的所有质因子，也是因为prime[j]是从小到大枚举的，prime[j] 也是 i*prime[j] 的最小质因子。

证毕。

2、这里为什么就要 break ？

因为 当前的 prime[j] 已经是 i 的最小质因子，如果不及时 break 掉，让循环继续，那么下一个 prime[j+1] * i 的最小质因子还是 prime[j] 而不是 prime[j+1]，这是因为i里面含有prime[j]这个质因子，它比prime[j+1]要小（从小到大枚举的） 。

所以要及时 break 。比如 {2,3,5} 当 i = 6时它筛掉是 12，而3*6 = 18不能继续筛，因为18的最小质因子也是2，而不是3.

3、如何保证所有的合数都能被筛掉？

举例合数x，当prime[j]是最小的质因子，当 i 枚举到 x / prime[j] 时候，就可以被筛掉。

每个合数只能被最小的质因子筛掉一次，因此是线性的。

总结： 在 $n$ 是 $10^6$ 左右的两者算法差不多。但在$10^7$线性筛比埃氏筛法快将近1倍。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com