质数

wzzwzy · 2026-07-06 15:52:52 · 算法·理论

质数

本文部分内容参考李煜东《算法竞赛进阶指南》

更新记录：

• 2026/7/8：质数部分基本完成

概述

::::info[质数的定义] 若一个正整数无法被除 1 和它自身之外的任何自然数整除，则称该数为质数（或素数），否则称该数为合数。特别地，1 既不是质数也不是合数。 ::::

::::info[质数的分布] 在整个自然数集合中，质数的数量不多，分布较为稀疏。对于一个足够大的正整数 N，不超过 N 的质数大约有 \dfrac{N}{\ln N} 个，即平均每 \ln N 个数中大约有 1 个质数。 ::::

一切判定和筛选质数的方法都是从定义出发的，请大家务必深入理解其本质。

一、质数的判定

1. 试除法

若一个正整数 N 是合数，则存在一个能整除 N 的整数 T，其中 2 \le T \le \sqrt{N}。

::::success[证明] 由质数定义可知，若 N 是合数，则存在一个能整除 N 的整数 M，其中 2 \le M \le N-1。

用反证法。假设命题不成立，即所有能整除 N 的数 M 都满足 \sqrt{N} < M \le N-1。因为 M 能整除 N，所以它们的商 N/M 也能整除 N。而 2 \le N/M < \sqrt{N}，令 T = N/M，这与假设矛盾。故假设不成立，原命题成立。

证毕。 ::::

根据上述命题，我们只需扫描 2 \sim \sqrt{N} 之间的所有整数，依次检查它们能否整除 N。若都不能整除，则 N 是质数；否则 N 是合数。试除法的时间复杂度为 O(\sqrt{N})。需要特别注意的是，0 和 1 既不是质数也不是合数，应单独处理。

::::info[代码实现]

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

::::

此外，还有一种效率更高的随机算法——Miller–Rabin 素性测试，但涉及较为深入的数学知识，我们将在后续章节中介绍。

二、质数的筛选

质数的筛选，顾名思义，就是像用筛子一样将质数从众多自然数中筛选出来，而非逐个判断每个数是否为质数。

1. Eratosthenes 筛法（埃氏筛）

任意整数 x 的倍数 2x, 3x, 4x, \dots 都不是质数——这由质数的定义显然可知。

我们可以从 2 开始，由小到大扫描每个数 x，将其倍数 2x, 3x, \dots, \lfloor N/x \rfloor \times x 标记为合数。当扫描到一个数时，若它尚未被标记，则它不能被 2 \sim x-1 之间的任何数整除，因此该数就是质数。

观察可以发现，2 和 3 都会将 6 标记为合数，存在重复标记。实际上，小于 x^2 的 x 的倍数在扫描更小的数时已经被标记过了。因此，可以对埃氏筛进行优化：对于每个数 x，只需从 x^2 开始，将 x^2, (x+1)x, \dots, \lfloor N/x \rfloor \times x 标记为合数即可。

::::info[代码实现]

void primes(int n) {
    memset(v, 0, sizeof(v)); // 合数标记，0 表示未标记
    for (int i = 2; i <= n; i++) {
        if (v[i]) continue;
        cout << i << endl; // i 是质数
        for (int j = i; j <= n / i; j++) v[i * j] = 1;
    }
}

::::

埃氏筛的时间复杂度为 O\left(\sum_{质数 p \le N} \frac{N}{p}\right) = O(N \log \log N)，已经非常接近线性。

2. 线性筛法（欧拉筛）

经过优化后的埃氏筛仍然会重复标记某些合数。线性筛法通过 “从大到小累积质因子” 的方式，保证每个合数只被标记一次。

设数组 v 记录每个数的最小质因子，按照以下步骤维护：

1. 依次考虑 2 \sim N 之间的每一个数 i。
2. 若 v[i] = 0，说明 i 是质数，将其保存下来，并令 v[i] = i。
3. 扫描所有不大于 v[i] 的质数 p，令 v[i \times p] = p。即在 i 的基础上累积一个质因子 p。因为 p \le v[i]，所以 p 就是合数 i \times p 的最小质因子。

每个合数 i \times p 只会被其最小质因子 p 筛一次，因此时间复杂度为 O(N)。

::::info[代码实现]

int v[MAX_N], prime[MAX_N];

void primes(int n) {
    memset(v, 0, sizeof(v)); // 最小质因子，0 表示未确定
    int m = 0; // 质数数量
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) {
            v[i] = i;
            prime[++m] = i; // i 是质数
        }
        // 给当前的数 i 乘上一个质因子
        for (int j = 1; j <= m; j++) {
            // i 含有比 prime[j] 更小的质因子，或超出 n 的范围，停止循环
            if (prime[j] > v[i] || prime[j] > n / i) break;
            // prime[j] 是合数 i * prime[j] 的最小质因子
            v[i * prime[j]] = prime[j];
        }
    }
    for (int i = 1; i <= m; i++) cout << prime[i] << endl;
}

::::

3. 习题

【模板】线性筛素数

三、质因数的分解

1. 算术基本定理

任何一个大于 1 的正整数都能唯一分解为有限个质数的乘积，可写作：

其中 c_i 都是正整数，p_i 都是质数，且满足 p_1 < p_2 < \cdots < p_m。

2. 试除法

结合质数判定中的试除法和质数筛选的思想，扫描 2 \sim \lfloor \sqrt{N} \rfloor 的每个数 d。若 d 能整除 N，则从 N 中除掉所有的因子 d，并同时累计 d 的个数。

因为一个合数的因子一定在扫描到该合数之前就被从 N 中除掉了，所以在上述过程中能整除 N 的 d 一定是质数。最终便得到了质因数分解的结果，时间复杂度为 O(\sqrt{N})。

特别地，若 N 没有被任何 2 \sim \sqrt{N} 的数整除，则 N 本身是质数，无需分解。

::::info[代码实现]

void divide(int n) {
    int m = 0;
    int p[MAX_N], c[MAX_N];
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) { // i 是质数
            p[++m] = i;
            c[m] = 0;
            while (n % i == 0) {
                n /= i;
                c[m]++;
            }
        }
    }
    if (n > 1) { // n 是质数
        p[++m] = n;
        c[m] = 1;
    }
    for (int i = 1; i <= m; i++)
        cout << p[i] << '^' << c[i] << endl;
}

::::

Pollard–Rho 算法是一种比试除法效率更高的质因数分解算法，感兴趣的读者可以参考此文。

3. 习题

阶乘分解