质数筛学习笔记

· · 算法·理论

判断质数

原理：根据质数定义，若 2 到 p-1 之间的所有数字都不是 p 的因数，则 p 是一个质数. 于是可以就此写出最简单的代码：

bool ok = true;
for(int i = 2; i < p; i++)
    if(p%i == 0) { ok = false; break; }
//ok = true 表示是质数, ok = false 表示是合数

时间复杂度 O(n).

优化

对于任意正整数 p，其一定能拆分成两个正整数的乘积，即：

p = xy

当 p 为合数时，必然存在一组 x 和 y，满足 x, y > 1.

我们令其中 x \leq y，则此时显然有 x \leq \sqrt{p} 且 y \geq \sqrt{q}. 这样的结论告诉我们，对于 p 的所有因数，其一定是成对出现的.

什么时候两边取等呢？显然当 p = x^2 = y^2，即 p 是个平方数时，其存在一组相同的 x 和 y.

于是我们判断 p 的因数时，只需要遍历到 \sqrt{p} 的范围即可.

代码：

bool ok = true;
for(int i = 2; i*i <= p; i++)
    if(p%i == 0) { ok = false; break; }
//为了不使用 sqrt，这里将式子两边同时平方

时间复杂度 O(\sqrt{n}).

分解质因数

这个过程类似于判断质数，不过实现方式只需要从小到大一一判断，然后将对应的质因子除去即可.

先给出代码：

for(int i = 2; i <= p; i++) {
    if(p%i == 0) {
        px[++tot] = i;
        while(p%i == 0) {
            cnt[tot]++;
            p /= i;
        }
    }
//px 表示分解出来的质因数数组
//tot 表示当前分解出来的质因数个数
//cnt 表示每个质因数在 p 里面出现的个数
}

可能你有所疑惑，为什么这里只需要判断 i 是否被 p 整除，便能保证 i 一定是 p 的质因子呢？

对于一个大于 1 的正整数来讲，其除了 1 以外的所有因数中，最小的那个因数也一定是他最小的那个质因数.

而代码中求质因数的顺序，也是从小到大枚举因数，这样就保证 “当 p 的最小质因数被找到并去除后，剩下的新的数字 p' 若不为 1 ，则一定存在一个新的最小质因数”.

因此这份代码不仅求出了 p 的质因数，而且在 px 数组中，你还会发现这些质因数一定是从小到大排序的.

此外……

还有一个东西叫 Pollard rho 算法，它能在 O(n^{1/4}) 的时间复杂度内对一个数字分解质因数，不过难度较大，且 noip 运用的可能性不大，因此我们仅做了解即可.

质数筛

埃氏筛

根据 “质数除本身以外的倍数都是合数”，当我们从 1 遍历到 i 时，可以用 1 到 i 之间已经找到的质数去枚举其倍数，然后将 i+1 到 n 之间的合数给打上标记. 最终没有被打上标记的便是质数.

代码：

for(int i = 2; i <= n; i++) {
    if(!vis[i]) {
        prime[++tot] = i;
        for(int j = 2; j*i <= n; j++)
            vis[i*j] = true;
    }
//prime 是用来存储筛出的质数的数组
//tot 表示当前筛出的质数总数
//vis 用来表示某个数字是否被打上标记（合数）
}

时间复杂度 O(n \log \log n).

线性筛

在埃氏筛中，每个数字可能被其质因数筛多次，而如果每个数字最多只被筛一次就好了. 于是线性筛算法为我们提供了这样一个模板：

for(int i = 2; i <= n; i++) {
    if(!vis[i]) prime[++tot] = i;
    for(int j = 1; j <= tot && i*prime[j] <= n; j++) {
        vis[i*prime[j]] = true;
        if(i%prime[j] == 0) break;
    }
}

时间复杂度 O(n)，这也是我们能找到的最优秀的质数筛算法.

另外，你还需要知道的是：在线性筛算法中，每个合数只会被其最小值因子筛掉，这个性质常用来线性求出一些数论函数的值，有相当大的实用价值.

下节课我们将会学习欧拉函数相关的内容，其中求解欧拉函数的方法将会与线性筛高度结合，因此请你牢记线性筛的相关内容.