线性筛法（欧拉筛）：不重复劳动的智慧

在编程的世界里，我们经常需要快速找出从1到n的所有质数（也叫素数）。比如老师让你列出全班40个学号中哪些是质数，或者你想知道100以内有多少个质数。你已经学过“埃拉托色尼筛法”（埃氏筛），它就像你拿着标尺，从2开始，把2的倍数全部划掉，然后3的倍数，5的倍数……但这样会有一个问题：一个数可能被划掉好几次。比如数30，它既是2的倍数，又是3的倍数，还是5的倍数，在埃氏筛里被重复标记了三次。这就好比洗碗时一个碗洗了三遍，浪费时间和精力。

有没有办法让每个合数只被划掉一次？有！那就是线性筛法，也叫欧拉筛。它的核心思想是：每个合数只被它的最小质因子（最小的那个质因数）筛掉。就像30的最小质因子是2，所以只让2来划掉30，3和5都不用管。这样每个合数只被处理一次，整个筛法的工作量和数字个数成正比，时间复杂度是O(n)，比埃氏筛的O(n log log n)更快。

为什么能做到“一次不重复”？—— 生活中的排队原理

想象一下学校发新课本，老师让每个同学来领一本书。为了避免重复发放，老师规定：每个同学只从自己学号对应的那桌领一次，领完就离开，不能回头。线性筛法的原理类似：我们从小到大遍历每个数i，用已知的质数p去标记合数i * p，但有一个重要的“停止规则”：当p能整除i（即i % p == 0）时，就立刻停止后面的乘法。为什么？

让我们用具体数字来理解。假设当前i=4，已知质数列表是[2, 3]。我们先用p=2，得到4*2=8，标记8为合数。检查4 % 2 == 0，成立，于是停止，不再用p=3去算4*3=12。为什么？因为12的最小质因子是2，将来当i=6时，用p=2会得到12（因为6*2=12），那时再标记一次就够了。现在如果i=4时也标记12，将来i=6又标记一次，就重复了。这个停止规则保证了每个合数只被它最小的质因子标记一次。

用数学语言说：如果p能整除i，那么对于任何更大的质数q（q > p），合数i * q的最小质因子其实是p，而不是q。因为i = p * k，所以i * q = p * (k * q)，显然p更小。如果我们现在就用q去标记，将来当i' = p * k（实际上就是i自己）时，会再次用p标记，造成重复。所以停在这里，把标记工作留给将来更合适的时机。

再举一个例子：i=6时，质数列表有[2, 3, 5]。用p=2得12，标记；6 % 2 == 0，停止。注意，这里不会用p=3去得18，因为18的最小质因子是2，将来i=9时用p=2会得到18（9*2=18），现在标记就早了。i=9时，用p=2得18，9 % 2 != 0，继续用p=3得27，9 % 3 == 0，停止。这样，18只被标记一次（在i=9、p=2时），27只被标记一次（在i=9、p=3时）。整个过程中，每个合数只出现一次。

从生活例子看“不重复劳动”

假设班级里有40个同学，学号1到40。老师想找出所有质数，但不想重复点名。线性筛法的做法是：让每个同学（从2到40）依次上台，手里拿着一张名单（已知质数）。老师规定：同学i用名单上的每个质数p去匹配，产生合数i * p，并把这个合数记到黑板上的“合数表”里。但有一个关键规则：如果p能整除i，那么同学i就不能再用后面的质数了，必须停止。这样，每个合数只会被第一次出现的那位同学记录一次。比如合数12，它会被同学6（因为62=12）记录，而不会被同学4（43=12）记录，因为同学4在碰到p=2时就停止了。这就避免了重复。

常见错误与调试技巧

新手在使用线性筛法时容易犯以下几个错误，需要特别注意：

错误1：忘记写break条件

如果没有if (i % p == 0) break;，那么代码就和埃氏筛没有区别了，每个合数会被多次标记，失去线性优势，甚至可能因为重复标记导致错误（虽然结果正确，但效率降低）。比如遍历到i=4时，如果没有break，会继续用p=3得到12并标记，然后i=6时又会用p=2标记12，这样12就被标记了两次。

错误2：数组越界

在标记is_prime[i * p] = false时，一定要先检查i * p是否超过n，否则会访问数组越界。代码中已经用if (i * p > n) break;来处理。

错误3：初始化遗漏

0和1不是质数，必须显式设置为false。很多新手忘记这一步，导致结果中可能包含0和1。

错误4：混淆了循环次序

外层循环for i是从2到n，内层循环遍历primes列表。注意，primes列表会随着外层循环逐渐增加，所以内层循环中i * p可能会大于n，必须用break跳出，否则会浪费计算或越界。

完整代码（含详细注释）

下面给出了C++和Python的完整实现，代码中已经对每一行变量定义添加了中文注释，方便理解。

C++ 代码

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

// 线性筛法（欧拉筛）：找出 1 到 n 的所有质数
vector<int> linear_sieve(int n) {
    vector<bool> is_prime(n + 1, true);   // is_prime[i] 表示 i 是否是质数（初始都认为是）
    vector<int> primes;                   // 存放找到的质数
    is_prime[0] = is_prime[1] = false;    // 0 和 1 不是质数

    for (int i = 2; i <= n; ++i) {
        // 如果 i 没有被标记为合数，说明它是质数
        if (is_prime[i]) {
            primes.push_back(i);          // 把 i 加入质数列表
        }
        // 用当前 i 去乘每个已经找到的质数，标记合数
        for (int p : primes) {
            if (i * p > n) break;        // 如果乘积超过 n，停止
            is_prime[i * p] = false;     // 标记 i*p 为合数
            if (i % p == 0) {            // 核心：如果 p 是 i 的因子，则停止
                break;
            }
        }
    }
    return primes;   // 返回质数列表
}

int main() {
    int n;
    cout << "请输入一个正整数 n：";
    cin >> n;
    vector<int> primes = linear_sieve(n);
    cout << "1 到 " << n << " 之间的质数有：" << endl;
    for (int p : primes) {
        cout << p << " ";
    }
    cout << endl;
    cout << "共 " << primes.size() << " 个" << endl;
    return 0;
}

运行示例

请输入一个正整数 n：30
1 到 30 之间的质数有：
2 3 5 7 11 13 17 19 23 29 
共 10 个

Python 代码

def linear_sieve(n: int):
    """线性筛法，返回 2 到 n 的所有质数列表"""
    is_prime = [True] * (n + 1)          # 标记数组，True 表示目前认为是质数
    is_prime[0] = is_prime[1] = False    # 0 和 1 不是质数
    primes = []                          # 存放质数

    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)             # 没被筛掉，是质数
        # 用 i 乘每个已知质数，标记合数
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False      # 标记合数
            if i % p == 0:               # 核心：p 是 i 的因子，停止
                break
    return primes

def main():
    n = int(input("请输入一个正整数 n："))
    primes = linear_sieve(n)
    print(f"1 到 {n} 之间的质数有：")
    print(' '.join(map(str, primes)))
    print(f"共 {len(primes)} 个")

if __name__ == "__main__":
    main()

运行示例

请输入一个正整数 n：30
1 到 30 之间的质数有：
2 3 5 7 11 13 17 19 23 29 
共 10 个

其他应用：线性筛法还能干什么？

线性筛法不仅用来求质数列表，它还能在筛的过程中轻松计算出每个数的最小质因子、欧拉函数、莫比乌斯函数等，为更高级的数论算法做预处理。例如，可以这样求最小质因子：

vector<int> min_prime(n + 1, 0);  // min_prime[i] 记录 i 的最小质因子
// 在标记合数时，如果 p 能整除 i，则 i*p 的最小质因子就是 p
// 并且 i 的最小质因子已经确定（就是 p，因为 p 是 i 的因子）
// 因此可以同时更新 min_prime[i*p] = p

如果你对求欧拉函数或莫比乌斯函数感兴趣，可以进一步学习“欧拉线性筛法”的扩展。

总结要点

1. 核心思想：每个合数只被它的最小质因子标记一次，避免重复劳动。
2. 关键代码：当 i % p == 0 时 break，确保不会用更大的质数去乘 i 而产生重复标记。
3. 时间复杂度：O(n)，比埃氏筛的 O(n log log n) 更快，尤其当 n 很大时优势明显。
4. 空间复杂度：O(n)，需要标记数组和质数列表。
5. 应用场景：求单段连续的质数列表（比如 1 到 10^7），或作为其他数论算法的预处理（比如求欧拉函数、莫比乌斯函数等）。
6. 注意：线性筛法不仅能筛质数，还能同时求出每个数的最小质因子、欧拉函数等，功能强大。

用线性筛法，就像班级里发奖品只发一次，效率高又不会混乱。同学们可以动手试试，用这个筛法找出更大范围内的质数，感受一下它的速度优势。如果你已经掌握了埃氏筛，现在学会线性筛，以后遇到需要快速质因数分解或模运算的问题时，就能派上大用场了！

相关学习指引

• 如果你还不太熟悉埃拉托色尼筛法，建议先回顾一下“埃氏筛”的原理，对比两者的区别。
• 学习如何用线性筛法同时求出每个数的欧拉函数（欧拉线性筛），这对数论竞赛题非常有用。
• 深入了解质因数分解算法（如试除法、Pollard's Rho），看看如何与线性筛结合。
• 尝试用线性筛法预处理质数列表，然后解决一些实际问题，比如判断一个大数是否为质数（用试除到sqrt(n)的质数即可）。