困难通用8 分钟2,862 字

线性筛法(欧拉筛)

在编程的世界里,我们经常需要快速找出从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++ 代码

cpp
#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 代码

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 个

其他应用:线性筛法还能干什么?

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

cpp
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)的质数即可)。

同类知识点