CC++ & Algorithm

筛法预处理与快速质因数分解

极难2
语言版本：通用
概述：先像筛子一样把小的质数都筛出来，然后用这些质数去分解任何大数，就像先准备好工具再干活一样高效。

先造工具再干活：用筛法预处理实现超快质因数分解

质因数分解，就是把一个合数写成几个质数相乘的形式。比如 12 = 2 × 2 × 3。如果只分解一两个数，你可以用“试除法”——从小到大试除质数，但当你需要分解成百上千个数时，每次从头试除就会非常慢。有没有什么好办法，能一口气把一大批数的质因数都快速分解出来呢？

有！筛法预处理就是答案。它就像先建一个“质数工具箱”，把所有能用的小质数提前找出来、排好队，然后分解任何一个数时，直接从工具箱里拿工具，又快又省力。更厉害的是，我们还可以给每个合数记下它的“最小质因子”（Smallest Prime Factor，简称SPF），这样分解时连试除都不需要，直接拿着 SPF 一路除下去就行。

下面我们就来学习这个强大的方法，看完之后你也能写出比试除法快几十倍的质因数分解代码。

一、生活中的类比：先修好“万能钥匙箱”

想象你是一个锁匠，接了一个大活儿：要修理学校里 1000 把锁，每把锁的锁芯结构都不同。如果你每修一把锁就现场车一把钥匙，那得累死。聪明的做法是：先花点时间，把所有可能用到的标准钥匙（即所有小质数）都打造好，放进一个工具箱。然后修锁时，只需从工具箱里拿出合适的钥匙试一下，不行再换下一把，效率就高多了。

筛法预处理就是这个道理。我们先一次性“筛”出某个范围内（比如 1 到 1 000 000）的所有质数，然后把这些质数存起来。以后不管分解哪个数，都只用这些预存的质数去试除，而不用从 2 开始重新判断是不是质数。更高级的做法是：在筛的过程中，顺便记录每个数的最小质因子（SPF），这样分解时连试除都省了，直接“跳”着除。

二、数学原理：从“埃氏筛”到“最小质因子数组”

1. 埃拉托斯特尼筛法（埃氏筛）——古人发明的“找质数神器”

要找出所有小于等于 N 的质数，古希腊数学家埃拉托斯特尼想了个绝妙的主意：

  • 先把 2 到 N 的所有数写下来，假设它们都是质数。
  • 从第一个质数 2 开始，把 2 的倍数（除了 2 本身）全部划掉（标记为合数）。
  • 然后看下一个没被划掉的数 3，它是质数，接着把 3 的倍数（除了 3）全部划掉。
  • 继续这样下去，每次找下一个没被划掉的数，它就是质数，再划掉它的倍数。
  • 最后剩下的、没被划掉的数就是质数。

这个方法很直观，但有一个小缺点：有些合数会被重复划掉多次。比如 6 既是 2 的倍数又是 3 的倍数，会被划两次。虽然不影响结果，但浪费了一点时间。埃氏筛的时间复杂度是 O(N log log N)，对于 N = 10⁷ 已经非常快。

2. 线性筛（欧拉筛）——每个合数只被标记一次，更快更省事

线性筛改进了埃氏筛，保证每个合数只被它的最小质因子标记一次，时间复杂度降到 O(N)。怎么做到的呢？

  • 维护一个质数列表 primes。
  • 从 i = 2 遍历到 N：
    • 如果 i 是质数（没被标记过），把它加入 primes。
    • 然后遍历质数列表中的每个质数 p：
      • 如果 i * p > N，停止。
      • 标记 i * p 为合数，并记录它的最小质因子为 p。
      • 如果 p 能整除 i（即 p 是 i 的因子），则 break（重要！这保证每个合数只被最小质因子标记一次）。

为什么这一步能保证“只被最小质因子标记”？因为当 p 能整除 i 时，对于更大的质数 p'，i * p' 的最小质因子一定是 p（因为 p 比 p' 小），所以后面不应该再由 p' 来标记。提前 break 就避免了重复。

3. 最小质因子数组（SPF）——分解的“超级快捷键”

在线性筛过程中，我们可以同时记录每个数的最小质因子，存到一个数组 spf 里：

  • 如果 i 是质数，spf[i] = i（因为质数的最小质因子就是它自己）。
  • 如果 i 是合数，在线性筛标记它时，spf[i * p] = p（p 是 i 乘以的那个质数，也是这个合数的最小质因子）。

有了 spf，分解一个数 x 就变成了一件简单到不能再简单的事情：

while x > 1:
    p = spf[x]       // 拿到当前数的最小质因子
    记录 p
    x = x / p        // 除掉这个因子

由于每次我们拿到的都是当前数的最小质因子，而最小质因子已经提前存好了，所以连试除都不需要，直接除法就行。整个过程的步数等于 x 的质因子个数（含重复），也就是 O(log x) 级别。对于 10⁷ 以内的数，几乎瞬间完成。

三、编程实现：把数学变成代码

下面我们用 C++ 和 Python 分别实现一个完整的例子：先用线性筛预处理出 1 到 100 万的 spf 数组，然后读入一个数，快速分解并打印出来。

代码中的变量名都用简短英文单词，每行变量定义都写了中文注释，方便你理解。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10000000; // 预处理的数范围，根据需求调整
vector<int> primes;        // 存储质数
vector<int> spf;           // 最小质因子数组，spf[i]表示i的最小质因子

// 线性筛，同时计算spf
void linear_sieve(int n) {
    spf.resize(n + 1);                     // 让spf有n+1个元素，索引从0到n
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) {                 // 如果spf[i]==0，说明i未被标记，i是质数
            spf[i] = i;                    // 质数的最小质因子就是它自己
            primes.push_back(i);           // 把i加入质数列表
        }
        // 遍历质数列表，用每个质数与i相乘
        for (int p : primes) {
            if (p > spf[i] || i * p > n)   // 保证每个合数只被最小质因子标记
                break;
            spf[i * p] = p;                // i*p的最小质因子设为p
        }
    }
}

// 利用spf分解质因数，返回质因子列表（包含重复）
vector<int> fast_factorize(int x) {
    vector<int> factors;
    while (x > 1) {
        int p = spf[x];                    // 获取x的最小质因子
        factors.push_back(p);              // 记录这个因子
        x /= p;                            // 除掉这个因子
    }
    return factors;
}

int main() {
    // 预处理[1, 1000000]范围内的spf
    linear_sieve(1000000);

    int num;
    cout << "请输入一个整数（<=1000000）: ";
    cin >> num;
    if (num <= 1) {
        cout << "输入必须大于1" << endl;
        return 0;
    }

    vector<int> res = fast_factorize(num);
    cout << num << " 的质因数分解: ";
    for (size_t i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i != res.size() - 1) cout << " * ";
    }
    cout << endl;

    // 验证：将分解结果乘回去看看是否等于原数
    long long product = 1;
    for (int f : res) product *= f;
    cout << "验证: " << product << (product == num ? " (正确)" : " (错误)") << endl;

    return 0;
}

Python 实现

def linear_sieve(n):
    """
    线性筛，返回 (质数列表, spf数组)
    spf[i] 表示i的最小质因子，若i是质数则spf[i]=i
    """
    primes = []               # 存储质数
    spf = [0] * (n + 1)       # spf数组，初始为0表示未被标记
    for i in range(2, n + 1):
        if spf[i] == 0:       # i是质数
            spf[i] = i
            primes.append(i)  # 加入质数列表
        # 用每个质数与i相乘
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p    # 标记合数的最小质因子
    return primes, spf

def fast_factorize(x, spf):
    """利用spf数组快速进行质因数分解，返回因子列表"""
    factors = []
    while x > 1:
        p = spf[x]            # 获取x的最小质因子
        factors.append(p)     # 记录
        x //= p               # 除掉
    return factors

def main():
    # 预处理100万以内的spf
    n_max = 1000000
    primes, spf = linear_sieve(n_max)

    try:
        num = int(input(f"请输入一个整数（<= {n_max}）: "))
        if num <= 1:
            print("输入必须大于1")
            return
        factors = fast_factorize(num, spf)
        print(f"{num} 的质因数分解: {' * '.join(map(str, factors))}")
        # 验证
        prod = 1
        for f in factors:
            prod *= f
        print(f"验证: {prod} {'(正确)' if prod == num else '(错误)'}")
    except ValueError:
        print("请输入有效整数")

if __name__ == "__main__":
    main()

四、新手容易犯的 3 个错误

  1. 忘记处理 n = 1
    1 不是质数也不是合数，spf[1] 没有意义。在分解函数中，如果输入是 1 或更小的数，应该直接返回空列表或报错，否则 while 循环永远不会结束（因为 spf[1] 未定义）。

  2. 线性筛中 break 条件写错
    很多初学者把 if (p > spf[i] || i * p > n) break; 写成 if (i * p > n) break;，这样会导致某些合数被重复标记（比如 12 会被 2×6 和 3×4 两次标记），效率下降，但通常不影响正确性。不过为了“线性”的名号，一定要加上 p > spf[i] 的判断。

  3. 数组大小没开够
    如果要分解的数 x 大于预处理的最大值 N，那么 spf[x] 会访问越界。解决办法是确保所有待分解的数都 ≤ N，或者用更大的 N 预处理。如果 N = 10⁷，spf 数组 int 类型大约占 40 MB，对于现代电脑还算可以，但 N = 10⁸ 就接近 400 MB，可能内存不够了。

五、完整示例：分解 123456

假设我们预处理了 1 到 1 000 000 的 spf，输入 123456：

  1. spf[123456] = 2 → 记录 2，x = 61728
  2. spf[61728] = 2 → 记录 2，x = 30864
  3. spf[30864] = 2 → 记录 2，x = 15432
  4. spf[15432] = 2 → 记录 2，x = 7716
  5. spf[7716] = 2 → 记录 2，x = 3858
  6. spf[3858] = 2 → 记录 2，x = 1929
  7. spf[1929] = 3 → 记录 3，x = 643
  8. spf[643] = 643（质数） → 记录 643，x = 1，结束。

所以 123456 = 2⁶ × 3 × 643。代码运行后会输出：123456 的质因数分解: 2 * 2 * 2 * 2 * 2 * 2 * 3 * 643。

六、进阶：用筛法分解区间内的所有数（区间筛）

有时你需要分解一个区间 [L, R] 内的所有数，比如 L = 10¹², R = 10¹² + 10⁶，直接开一个 10¹² 的数组显然不可能。但我们可以只筛出 √R 以内的质数（约 10⁶），然后用这些质数去“标记”区间内的合数，并记录每个合数的最小质因子。这种方法叫做区间筛，在编程竞赛中很常见。具体思路是：

  • 先筛出 1 到 √R 的所有质数。
  • 对于每个质数 p，找到它在 [L, R] 内的第一个倍数，然后开始标记，同时记录最小质因子。
  • 最后，区间内那些没有被标记的数就是质数，它们的质因子就是它们自己。

区间筛可以让你用 O(√R log log R + (R-L) log log R) 的时间分解一大段区间内的所有数，非常高效。有兴趣的话可以自己动手实现一下。

七、练习

  1. 修改代码，输出每个质因子的指数（比如 12 = 2² × 3，而不是 2 * 2 * 3）。
    提示：在 fast_factorize 中，当连续获取相同因子时，可以计数。建议用字典或 pair 保存（质因子，指数）。

  2. 写一个程序，读入整数 N，输出所有 2~N 的数的质因数分解，每行一个数。
    提示：先预处理 spf，然后对每个数调用 fast_factorize。注意分解结果可以按格式打印，比如 6 = 2 * 3。

  3. 思考题：如果 spf 数组使用 short 类型（2 字节）存储，最大能支持多大的 N？有什么风险？
    提示：short 能表示的最大值是 65535，所以 N 只能 ≤ 65535。如果 N 更大，spf 值会溢出（比如 65536 的最小质因子是 2，但 65536 超出了 short 范围，会被截断成负数或错误值）。所以用 short 要谨慎，通常用 int 或 unsigned int 更安全。

八、相关指引

  • 如果你对埃氏筛和线性筛的原理还不太清楚，可以搜索“埃拉托斯特尼筛法”和“欧拉筛”的详细教程。
  • 筛法预处理不仅用于质因数分解，还常用于求欧拉函数 φ(n)、莫比乌斯函数 μ(n) 等数论函数。
  • 如果遇到需要分解 10¹⁸ 级别的大数（比如 RSA 密码中的大数），筛法就无能为力了，这时需要学习 Miller-Rabin 素性测试 和 Pollard Rho 质因数分解算法。它们不需要预处理，但速度也很快。

希望这篇文章能帮你理解“先造工具再干活”的筛法预处理思想。以后遇到需要大量分解质因数的题目，记得先用线性筛把 SPF 数组准备好，然后就能以闪电般的速度解决问题啦！

例题精讲

1单选题

在使用线性筛预处理得到每个数的最小质因子（lpf）数组后，要分解一个正整数n（n ≤ 10^7）的质因数，以下哪种做法最合理？

A从2到√n枚举所有质数，试除
B从质数列表中依次取出质数，判断是否能整除n
C循环 while n > 1: 取出 lpf[n]，记录，然后 n /= lpf[n]
D从2开始枚举所有整数，试除
2判断题

在埃拉托斯特尼筛法中，我们只需从2到√n的每个数进行标记，就可以得到所有不超过n的质数。

3填空题
已知数组 lpf[0..MAXN] 已通过线性筛预处理，lpf[i] 表示 i 的最小质因子。以下函数 decompose 用于打印 n 的质因数分解（如 12 = 2^2 * 3^1）。请填空完成代码。
void decompose(int n) {
    while (n > 1) {
        int p = lpf[n];
        int cnt = 0;
        while (___) {
            ___;
            ___;
        }
        printf("%d^%d ", p, cnt);
    }
}
4单选题

关于线性筛（欧拉筛）和埃拉托斯特尼筛法的区别，以下哪个说法是正确的？

A线性筛的时间复杂度是O(n log log n)，埃氏筛是O(n)
B线性筛可以保证每个合数只被其最小质因子筛掉一次
C埃氏筛比线性筛更快，因为不需要存储每个数的最小质因子
D线性筛只能用于筛选质数，不能用于计算最小质因子
5判断题

在使用筛法预处理得到最小质因子数组后，快速质因数分解的时间复杂度是O(√n)。