线性筛法：每个合数只筛一次，更快更聪明

开场：什么是线性筛法，用来干什么？

假如你想知道从2到1亿之间有哪些质数（只能被1和它自己整除的数），最笨的方法是一个数一个数去试除，那太慢了。后来人们发明了“埃氏筛法”，它就像从一堆数里划掉所有合数，但划的时候会重复划掉同一个数，比如12会被2和3各划一次。如果数很大，重复的划痕就特别浪费时间。

线性筛法就是在埃氏筛法基础上改进的算法，它保证每个合数只被它的最小质因子筛掉一次，每个数只访问一次，所以速度更快，在计算机竞赛和编程中非常常用。简单说，它是一张更聪明的筛子，能又快又准地找出所有质数。

分点讲解：关键概念 + 例子 + 代码

1. 为什么会有重复标记？——用生活例子理解

想象你有一张从2到20的号码牌，你想找出所有质数。埃氏筛法的做法是：从2开始，把2的所有倍数（4,6,8,…）划掉；然后看3，把3的倍数（6,9,12,…）划掉；然后看5……你看，12既被2划了一次（因为2×6=12），又被3划了一次（3×4=12）。这种重复划掉在范围很大时累积起来，就会拖慢速度。

线性筛法怎么避免呢？它规定：每个合数只由它最小的质因子来划掉。比如12的最小质因子是2，那就在标记2×6=12时划掉它，之后3×4=12就不会再去划了。这样每个合数只被标记一次，效率翻倍。

2. 最小质因子是什么？——先搞清楚概念

一个合数（比如30）的质因子有2、3、5，其中最小的那个（2）就是它的最小质因子。线性筛法的核心思路就是：当我们遍历每个数 i 时，用已经找到的质数 p 去乘得到合数 i×p，并且保证 p 恰好是这个合数的最小质因子。怎么保证呢？这就是下面要说的 break 条件。

3. 关键步骤：for 循环 + 内层 for + break

看下面这段代码（这是扩展后的版本，每行变量都有中文注释）：

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

int main() {
    int n = 100;                     // 求2~n之间的质数
    vector<bool> isPrime(n + 1, true); // 标记是否为质数，初始全部为true
    vector<int> primes;              // 存放质数的数组
    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    for (int i = 2; i <= n; i++) {   // 从2开始遍历每个数
        if (isPrime[i]) {            // 如果i没被标记为合数，说明它是质数
            primes.push_back(i);     // 把i加入质数列表
        }
        // 用当前质数列表中的每个质数去标记合数
        for (int p : primes) {       // p是已经找到的质数
            if (i * p > n) break;    // 超出范围就停止
            isPrime[i * p] = false;  // 标记i×p为合数
            if (i % p == 0) break;   // ★关键：如果p是i的因子，则停止内层循环
        }
    }

    // 输出结果
    cout << "2到" << n << "之间的质数有：";
    for (int x : primes) cout << x << " ";
    cout << endl;
    return 0;
}

解释一下那个break为什么是关键

想象我们在跑循环，i=2时：

• 质数列表为空？不对，i=2是质数，先加入列表，然后内层循环只有一个p=2，标记4为合数，检查i%p=2%2==0，break。这时筛掉了4（最小质因子2）。

i=3时：

• 3是质数，加入列表。内层循环先p=2，标记6，i%p=3%2≠0，继续；然后p=3，标记9，i%p=3%3==0，break。筛掉了6（最小质因子2？等等，6的最小质因子是2，这里p=2时标记了6，是对的，但继续到p=3时标记了9，9的最小质因子是3，也正确）

i=4时：

• 4是合数，所以不会加入列表。内层循环p=2，标记8，i%p=4%2==0，break。筛掉了8（最小质因子2），注意：如果在p=2之后继续，还会标记4×3=12，但那样p=3就不是8的最小质因子了，所以break保证了只标记i×p且p≤i的最小质因子。

i=6时：

• 6不是质数，内层p=2，标记12，现在i%2=6%2==0，break。12被p=2（最小质因子）筛掉了。之后不会用p=3再去筛12，因为已经break了。

所以每个合数都只被它最小的质因子筛掉，且只筛一次。

4. 用一个小例子手动模拟（n=10）

最终质数：2,3,5,7。合数4,6,8,9,10都被标记一次，没有重复。

新手容易犯的错误

❌ 错误1：忘记写 break 条件

如果不写 if (i % p == 0) break;，代码就退化成了埃氏筛法，每个合数会被它的每个质因子重复标记。比如i=6时，p会遍历2,3,5，标记12,18,30，其中12被标记两次（p=2和p=3都标了），结果虽然正确但效率降低。

❌ 错误2：只初始化了 isPrime[0] 和 isPrime[1]，但忘了 vector 的默认值

vector<bool> isPrime(n+1, true); 已经默认全是true，所以只需要单独设置0和1为false。但如果写成 vector<bool> isPrime(n+1); 没有第二个参数，则默认是false，那就要先全部置true，或者反过来标记合数。新手容易混淆。

❌ 错误3：内层循环的边界判断顺序

if (i * p > n) break; 要放在标记之前，否则 i * p 可能溢出（当n接近int最大值时）。保险的做法是用 if (i > n / p) break; 避免乘法溢出。

❌ 错误4：以为质数列表大小固定

有些人会先估计质数个数，用静态数组。其实用 vector<int> 动态增长最方便，不用担心空间浪费，因为质数个数大约只有n/ln(n)。

完整可运行的代码示例（带输出质数个数）

下面代码会输出质数列表和质数总数，方便验证。

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

int main() {
    int n = 100;                     // 求2~n之间的质数，可以改成任意正整数
    vector<bool> isPrime(n + 1, true); // 标记数组，true表示是质数
    vector<int> primes;              // 存放所有找到的质数
    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    for (int i = 2; i <= n; i++) {   // 遍历每个数
        if (isPrime[i]) {            // 如果i是质数
            primes.push_back(i);     // 加入质数列表
        }
        // 用已有质数去筛合数
        for (int p : primes) {       // p是当前质数
            if (i * p > n) break;    // 超出范围，直接跳出
            isPrime[i * p] = false;  // 标记i×p为合数
            if (i % p == 0) break;   // 关键：p是i的因子时停止
        }
    }

    // 输出结果
    cout << "2到" << n << "之间的质数共有" << primes.size() << "个，分别是：\n";
    for (int x : primes) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

运行结果：

2到100之间的质数共有25个，分别是：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

线性筛法为什么快？——简单对比

埃氏筛法的时间复杂度是 O(n log log n)，而线性筛法是 O(n)。在n=10⁷时，线性筛法大约比埃氏筛法快一倍；n越大，优势越明显。所以做竞赛题时，如果数据范围很大（比如n=10⁷），一定要用线性筛法。

另外，线性筛法还能顺便求出每个数的最小质因子（在标记时记录），这对后续分解质因数、求欧拉函数等都非常有用。

相关知识点指引

如果你学懂了线性筛法，接下来可以看看：

• 埃氏筛法：线性筛法的基础，理解它才能理解为什么要改进。
• 质因数分解：利用线性筛法求出每个数的最小质因子，就可以快速分解任意数。
• 欧拉函数（φ函数）：用线性筛法可以O(n)求出1~n所有数的欧拉函数值，这是数论中很重要的工具。
• 莫比乌斯函数：类似地，线性筛法也可以用来求莫比乌斯函数。
• 积性函数：线性筛法可以处理很多积性函数，是数论进阶的基础。

把这些串联起来，你就能掌握一大块数论算法，在编程竞赛中游刃有余啦！