筛法

我们想要知道小于等于 $n$ 的自然数中有多少素数，对于每个数都进行暴力素数判断的时间复杂度为 $O(n\sqrt n)$，这是无法接受的；因此我们需要更高效的筛法

1. 埃氏筛

对于每个大于 $1$ 的数 $i$，我们筛掉除它自己外它的所有倍数，这样最后剩下的数全为素数

埃氏筛的时间复杂度为 $O(n\log \log n)$

实现时有几个小优化： 1. 显然 $n$ 以内所有的合数都可以被 $\sqrt n$ 及以内的数标记到，因此只筛到 $\sqrt n$ 即可 2. 当我们筛到数 $i$ 时，易知合数 $2 \times i, 3 \times i, ..., (i-1) \times i$ 都被之前筛过的数 $2, 3, ..., (i-1)$ 标记过了，因此直接从 $i \times i$ 开始标记即可 3. 因为除了 $2$ 的偶数都不会是素数，所以可以只筛奇数，最终统计时也只统计奇数即可 4. 可以使用 $bitset$ 或 $vector<bool>$ 代替传统的 $bool$ 数组优化常数

代码中的 $ui$ 为 $unsigned\ int$，下同

C++
vector<ui> ErSieve(ui n){
    vector<ui> primes;
    vector<bool> is_prime(INF, true);   
    is_prime[0] = is_prime[1] = false;
    primes.push_back(2);

    for (ui i=3; i*i<=n; i+=2){
        if (is_prime[i] == true){
            for (ui j=i*i; j<=n; j+=i) is_prime[j] = false; 
        }
    }
    for (ui i=3; i<=n; i+=2){
        if (is_prime[i] == true) primes.push_back(i);
    }
    return primes;  
}

2. 欧拉筛

埃氏筛非线性的原因在于合数可能会被重复标记，如 $12$ 就会被 $2$, $3$ 各标记一次；欧拉筛省掉了这些无意义的步骤，使得算法效率更高

在欧拉筛中，我们使每个合数都 只被其最小质因数筛掉；具体的，在筛到数 $i$ 时，我们从小到大枚举每个质数 $primes[j]$，期望 $primes[j]$ 是 $i \times primes[j]$ 的最小质因数并筛掉 $i \times primes[j]$；那么如何保证这一性质？当满足 $i \% primes[j] = 0$ 时不再继续往下枚举 $primes[j]$

首先证明所有的合数都可以被这么筛掉；任取合数 $num$，记其最小质因数为 $p$，则 $num$ 可被分解为 $p \times num'$；在外层循环枚举到 $num'$ 时，设 $num'$ 的最小质因数为 $q$，显然有 $q \ge p$，因此在枚举到 $q$ 并不再继续枚举 (及) 之前时一定能够枚举到 $p$ 并删去 $num$；又由于 $num$ 可以任取，则得证

其次证明这么筛没有问题；具体的，对外层枚举到的数 $i$ 与内层枚举到的质数 $primes[j]$，即证对于在 $i \% primes[j]=0$ 之前的所有 $primes[j']$，都有 $primes[j']$ 是 $i \times primes[j']$ 的最小质因数；对于在 $i \% primes[j]=0$ 之后的所有 $primes[j'']$，都有 $primes[j'']$ 不是 $i \times primes[j'']$ 的最小质因数；

后一条是显然的，由于内层从小到大枚举，一定有 $primes[j] < primes[j'']$，那么 $i \times primes[j'']$ 的最小质因数一定小于等于 $primes[j]$，不可能是 $primes[j'']$

前一条也可以用类似的方法进行反证，对于 $i \times primes[j']$，若存在一个更小的最小质因数，那么内层一定循环不到 $primes[j']$ (在更小的最小质因数那里就已经会结束了)

每个合数只会被筛一次，时间复杂度就是 $O(n)$ 的

C++
vector<ui> EuSieve(ui n){
    vector<ui> primes;
    vector<bool> is_prime(INF, true);
    is_prime[0] = is_prime[1] = false;

    for (ui i=2; i<=n; i++){
        if (is_prime[i] == true) primes.push_back(i);
        for (ui j=0; j<primes.size() && i*primes[j]<=n; j++){
            is_prime[i*primes[j]] = false;
            if (i % primes[j] == 0) break;  
        }
    }
    return primes;
}

两种筛法的比较

事实上，埃氏筛的时间复杂度并不一定比欧拉筛劣，在 $OI$ 下常用的 $1e8$ 的数据范围内 $\log \log n$ 可以看做一个很小的常数 (大约为 $4$)，加上上文提及的几个优化，性能甚至比欧拉筛要好 (参见 OI-wiki 的效率测试)；在空间复杂度上，两者是相同的

如果不需要进行其他应用，只是筛素数的话可以用埃氏筛；反之，如求欧拉函数、因数个数时，则用欧拉筛更好

3. 欧拉筛的应用

求最小质因数

这是显然的。欧拉筛的过程已经保证了在筛到合数 $i \times primes[j]$ 时，$primes[j]$ 就是其最小质因数；我们只需要记录一下即可

求欧拉函数

对于数 $i$，欧拉函数的定义为小于等于 $i$ 且与 $i$ 互质的数的个数；欧拉函数是 积性函数；我们 按照 $i \% primes[j]$ 进行分类讨论：

若 $i \% primes[j] = 0$，这说明 $i$ 中 包含 $i \times primes[j]$ 的全部质因子；展开式子，代入 $num = i \times primes[j]$ $$ \varphi(num) = num \times \prod_{k=1}^{c} (1-\frac{1}{p_k})\ = i \times primes[j] \times \prod_{k=1}^{c} (1-\frac{1}{p_k})\ = (i \times \prod_{k=1}^{c} (1-\frac{1}{p_k})) \times primes[j]\ = \varphi(i) \times primes[j] $$ 综上，此时 $\varphi(i \times primes[j]) = \varphi(i) \times primes[j]$

若 $i \% primes[j] \ne 0$，则说明 $i$ 与 $primes[j]$ 互质；根据积性函数的定义，有 $$ \varphi(i \times primes[j]) = \varphi(i) \times \varphi(primes[j])\ \varphi(i \times primes[j]) = \varphi(i) \times (primes[j]-1) $$ 综上，此时 $\varphi(i \times primes[j]) = \varphi(i) \times (primes[j]-1)$

注意为 $i$ 为质数时，需要特判 $\varphi(i) = i-1$，另外记得设初值 $\varphi(1) = 1$

求因数个数

定理：将数 $n$ 进行质因数分解，设 $n=\prod_{i=1}^{m} p_i^{c_i}$，由乘法原理易知 $n$ 有 $\prod_{i=1}^{m} (c_i+1)$ 个因数

我们考虑设 $dc_i$ 表示数 $i$ 的因数个数，$ec_i$ 表示数 $i$ 的最小质因数的出现次数 (指数)，$num = i \times primes[j]$；按照 $i \% primes[j]$ 分类讨论

若 $i \% primes[j]=0$，说明 $i$ 中包含 $num$ 的全部质因数，区别只在最小质因数 $primes[j]$ 的出现次数少了 $1$，有 $ec_{num} = ec_i+1$；展开 $dc_{num}$ 与 $dc_i$ $$ dc_{num} = \prod_{i=1}^{m}(c_i+1) = \prod_{i=2}^{m} (c_i+1) \times (ec_{num}+1)\ dc_{i} = \prod_{i=1}^{m}(c_i+1) = \prod_{i=2}^{m}(c_i+1) \times (ec_i+1) $$ 两式相除，得到 $$ \frac{dc_{num}}{dc_{i}} = \frac{ec_{num}+1}{ec_i+1}\ \frac{dc_{num}}{dc_{i}} = \frac{ec_{num}+1}{ec_{num}} $$ 综上，有 $dc_{num}=dc_{i} \times \displaystyle \frac{(ec_{num}+1)}{ec_{num}}$

若 $i \% primes[j] \ne 0$，说明 $i$ 中不包含 $primes[j]$，那么 $num$ 中只含 $1$ 个 $primes[j]$，即 $ec_{num}=1$；我们仿照上面 把 $dc_{num}$ 中 $primes[j]$ 一项的出现个数单拆出来 即可，其余的正好是 $dc_i$ $$ dc_{num} = \prod_{i=1}^{m}(c_i+1) = \prod_{i=2}^{m}(c_i+1) \times (1+1) = dc_i \times 2 $$ 综上，有 $dc_{num} = dc_i \times 2$

同样注意 $i$ 为质数时，特判 $dc_i=2, ec_i=1$ 即可

求因数和

定理：将数 $n$ 进行质因数分解，设 $n=\prod_{i=1}^{m} p_i^{c_i}$，易知 $n$ 的因数和为 $\prod_{i=1}^{m} \sum_{j=0}^{c_i}(p_i^j)$，相当于任选每个 $p_i$ 上的指数 $j$

我们考虑设 $ds_i$ 表示数 $i$ 的因数个数，$es_i$ 表示数 $i$ 的最小质因数的等比数列求和 (即 $\sum_{i=0}^{c_{p}} p^i$)，$num = i \times primes[j]$；仍然按照 $i \% primes[j]$ 分类讨论 (以下简写 $primes[j]$ 为 $p$)

若 $i \% primes[j]=0$，则 $num$ 中只比 $i$ 多一个 $p$，记 $i$ 中有 $c_p$ 个 $p$，我们打开 $es_{num}$ 与 $es_i$ 进行比较 $$ es_{num} = p^0+p1+p^2+...+p\ es_{i} = p^0+p1+p^2+...+p $$ 观察到基本只差一个 $p$，不妨乘上去，则得到 $$ es_{num} = es_{i} \times p + p^0 $$ 因此，有 $es_{num} = es_{i} \times p + 1$；由于在等比数列求和的形式下不方便直接比较 $ds_{num}$ 与 $ds_{i}$，不妨直接套用公式简化为 $$ \sum_{i=0}^{c_{p}} p^i = \frac{p^{c_p+1}-1}{p-1} $$ $ds_{num}$ 与 $ds_i$ 差的实际上只有这一项，直接相除 $$ \frac{ds_{num}}{ds_i} = \frac{p^{c_p+2}-1}{p\ \frac{ds_{num}}{ds_i} = p + \frac{p-1}{p^{c_p+1}-1} $$ 在分数的上下同除 }-1$p-1$，变回等比数列求和的形式 $$ \frac{ds_{num}}{ds_i} = p + \frac{1}{\sum_{i=0}^{c_{p}} p^i}\ \frac{ds_{num}}{ds_i} = \frac{p \times \sum_{i=0}^{c_{p}} p^i + 1}{\sum_{i=0}^{c_{p}} p^i} $$ 神奇的事情出现了！此时上下两项刚好分别是 $es_{num}$ 与 $es_i$，即 $$ \frac{ds_{num}}{ds_i} = \frac{es_{num}}{es_i}\ $$ 综上，$ds_{num} = {ds_i} \times \displaystyle \frac{es_{num}}{es_i}$

若 $i \% primes[j] \ne 0$，则 $num$ 中只包含一个 $p$，那么 $es_{num} = p+1$；$ds_{num} = (es_{num}) \times ds_i$，即有 $ds_{num} = (p+1) \times ds_i$

同样注意在 $i$ 是质数时，特判 $ds_i = p+1, es_i = p+1$

后记

~~抄袭了~~ 参考了 masonxiong 大佬的 blog

筛法