质数

质数是指在大于 1 的自然数中，除了 1 和它本身以外 不再有其他因数 的自然数。

质数的判定

质数的判定方法：试除法

最暴力的写法：判断 $n$ 是否为素数的时间复杂度为 $O(n)$。

bool is_prime(int n) {
    if (n < 2) {
        return false;
    }

    for (int i = 2; i < n; i ++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

注意到，如果 $d|n$，那么 $(n/d)|n$。也就是说，我们枚举的时候可以只枚举较小的可能因子，即 $d\le (n/d)$，因此 $d\le \sqrt{n}$。降低时间复杂度到 $O(\sqrt{n})$。

这里的 for 循环就有很多细节了：

• i <= sqrt(n) 这种写法会多次执行求根号操作，很慢
• i * i <= n 这种写法也不推荐，当 n->2147483647 时，此时 i * i 可能会爆 int
• i <= n / i 推荐这种写法，这种写法是不会漏掉任何一个因子的

分解质因数

分解质因数：试除法，从小到大尝试所有因数，一样只需要枚举到 $\sqrt{n}$ 即可。

最暴力的写法：

void divide(int n) {
    for (int i = 2; i <= n; i ++) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                s ++;
            }
            cout << i << s << endl;
        }
    }
}

上面看似是从小到大枚举所有数（而非质因数），但其实这样做是不会枚举到合数的，因为当我们枚举到 $i$ 时就意味着此时的 $n$ 中已经不包含所有 $2\sim i-1$ 中的质因子了（被除干净了），因此 $i$ 只能为质数才能成为 $n$ 的因子。

同时我们还注意到：$n$ 中最多只包含一个 $>\sqrt{n}$ 的质因子（否则这两个一乘就超过 $n$ 了）。因此我们可以先除掉 $n$ 中所有不超过 $\sqrt{n}$ 的质因子，最后单独处理这个大因子。时间复杂度会降低到 $O(\sqrt{n})$。

• 质数判定：时间复杂度一定为 $O(\sqrt{n})$
• 分解质因数：时间复杂度最坏为 $O(\sqrt{n})$，最好为 $O(\log n)$

筛质数

给定一个正整数 $n$，请你求出 $1\sim n$ 中质数的个数。

算法流程：

• 对于 $i$，删除它以及它的所有倍数
• 当轮到 $i$ 时，如果它之前没有被删除，说明它是质数 $p$
• 这是因为这样表明 $2\sim p-1$ 中没有一个是它的因数，这正是质数的定义

AC868. 筛质数

void get_primes(int n) {
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) {
            primes[cnt ++] = i;
        }

        for (int j = i + i; j <= n; j += i) {
            st[j] = true;
        }
    }
}

时间复杂度：对于 $i$，它需要循环 $n/i$ 次，因此总的时间复杂度为：

$$\frac{n}{2}+\frac{n}{3}+\cdots +\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n})\approx n\ln n$$

埃氏筛

可以不删除所有数的倍数，只删除质数的倍数即可（不能再小了）。

void get_primes(int n) {
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) {
            primes[cnt ++] = i;

            for (int j = i + i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}

质数定理：$1\sim n$ 中大约有 $n/\ln n$ 个质数，因此我们这个算法是原来算法时间复杂度的 $1/\ln n$，也就是 $O(n)$ 的（这是不对的，真实的时间复杂度为 $O(n\log n\log n)$，而这个常数已经近似为 1 了）。

这个算法由希腊数学家埃拉托色尼 Eratosthenes 发明，因此也被称为 埃氏筛。

线性筛

算法流程：

• 对于每个数 i 从小到大枚举所有的质数
• 将 i * p 筛掉
• 如果 i 中已经含有 p 这个质因子，就 break

void get_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;
            }
        }
    }
}

举个例子：

$n$	$i\times j$	st
$2$	$2\times 2$	true
$3$	$3\times 2,3\times 3$	true
$4$	$4\times 2$	false
$5$	$5\times 2,5\times 3,5\times 5$	true
$6$	$6\times 2$	false

由表格可知：任意数 n 只会被它的最小质因子筛掉，例如 12，它只会被 2 筛掉。

当我们执行 if (i % primes[j] == 0) break; 的时候

• 成立：
  • 说明此时的 p 一定是 i 的最小质因子
  • 同时它就一定是 primes[j] * i 这个合数的最小质因子
  • 由于此时的 i 至少含有一个 p，如果继续从小到大枚举质数的话，下一个 primes[j + 1] * i 就一定不是用最小质因子 p 筛掉合数了，因此停止
• 不成立：
  • 说明此时的 p 一定小于 i 的所有质因子
  • 所以此时 primes[j] * i 的最小质因子也还是 p
• 因此我们执行 st[primes[j] * i] = true; 时，事实上就是用合数的最小质因子筛掉了它

刚才已经说明：所有被筛掉的合数都是被它的最小质因子筛掉的，接下来说明：所有的合数都会被筛掉。

• 对于合数 x，假设 p 是 x 的最小质因子
• 当 i 枚举到 x / p 的时候，一定会被内层循环筛掉
• 每个数只会被筛一次，因此该筛法是 线性的

三种筛法的比较：

• 10^7
  • 普通筛：1.606
  • 埃氏筛：0.316
  • 线性筛：0.098
• 10^8
  • 普通筛：28.134
  • 埃氏筛：3.756
  • 线性筛：0.948