线性筛法 - 五级 | C++ & Algorithm 编程研习社

线性筛法——让每个合数只被“筛”一次

你小时候有没有排队领过奖品？如果每个人只能领一次，老师就会按顺序叫名字，叫到的人去领，没叫到的不去。但假如老师不小心叫了同一个人两次，那排队时间就变长了。埃氏筛法找质数时，就有点像这种“重复点名”——比如数字6，会被质数2和3各“点名”一次，造成浪费。有没有办法让每个数字只被点名一次？有！这就是线性筛法（也叫欧拉筛法）。它保证每个合数只被它的最小质因子筛掉，速度更快，就像排队时每个人只被叫一次，时间就是 O(n)，真正的“线性时间”。

1. 为什么需要“线性筛”？

先回忆一下埃氏筛法的做法：从2开始，把每个质数的倍数都标记成合数。比如：

用质数2，标记4、6、8、10……
用质数3，标记6、9、12、15……

看到问题了吗？数字6既被2标记，又被3标记，被重复标记了。当你要找100万以内的质数时，这种重复会浪费大量时间。而线性筛法就是专门解决这个问题的——每个合数只被它最小的质因子标记一次，绝不重复。

2. 线性筛的核心：最小质因子“一刀切”

想象你手里有一个“质数名单”（列表 primes），里面装着已经找到的质数。然后你从左到右遍历每个数字 i（从2开始），做两件事：

如果 i 是质数，就把它加入名单。
用 i 去乘名单里的每个质数 p，得到合数 i*p，并标记这个合数为“不是质数”。但是，一旦发现 p 是 i 的因子（即 i % p == 0），就立即停止，不再乘更大的质数。

为什么要停止？因为如果继续用更大的质数去乘 i，得到的合数的最小质因子其实是当前的 p，而不是那个更大的质数。比如：

当 i = 4 时，名单里有 [2, 3]。先算 4*2 = 8，标记8为合数。因为 4 % 2 == 0，所以停止，不再算 4*3 = 12。
为什么不算12？因为12的最小质因子是2，它会在未来 i = 6 时被 6*2 = 12 标记。如果现在标记了，将来又会重复标记。每个合数只交给它的最小质因子去处理，这样就能保证每个合数只被标记一次。

3. 代码一步一步拆解（附生活例子）

下面这段代码就是线性筛法的Python实现。每一行都加了中文注释，方便你理解。

def linear_sieve(n):
    # 创建一个布尔数组，初始都当作质数（True），下标从0到n
    is_prime = [True] * (n + 1)
    primes = []                     # 存放找到的质数

    for i in range(2, n + 1):       # 从2开始遍历每个数字
        if is_prime[i]:
            primes.append(i)        # i是质数，加入列表（相当于“新班长”被选出来）
        
        # 用已有质数 p 来筛选合数 i * p
        for p in primes:
            if i * p > n:           # 超过范围，直接结束循环
                break
            is_prime[i * p] = False  # 标记 i*p 为合数（相当于“这人不合格”）
            
            # 关键判断：如果 p 是 i 的因子，就停止，避免重复标记
            if i % p == 0:
                break
    return primes

# 测试：输出50以内的质数
print(linear_sieve(50))

举个生活例子帮你理解：假设学校要给每个班级分发奖品，每个班只有一个“最小学号”的同学负责领奖。如果班上有很多人，我们只让学号最小的同学去领，其他同学即使有机会也不去。线性筛法里，i 就像当前排队的班级，p 是已经选出的“最小质因子”（学号最小的班长）。如果当前班级里已经有更小的班长（即 i % p == 0），那么更大的班长（更大的质数）就不需要来管这个班级了，因为他们管出来的合数会被更小的班长以后处理。

4. 新手最容易犯的错误

忘记 break 条件：如果把 if i % p == 0: break 删掉，代码就变成了埃氏筛法（只是用质数列表乘 i，没有及时停止），效率降低，还可能标记重复。
越界问题：i * p 可能超过 n，所以要先检查 if i * p > n: break。在Python中，整数可以很大，但列表长度有限，不检查会报下标越界错误。
is_prime 数组初始值：要确保 is_prime[0] 和 is_prime[1] 为 False（0和1不是质数）。上面代码省略了这一步，因为遍历从2开始，但最好在最开始显式设置 is_prime[0] = is_prime[1] = False，以免后续不小心用到它们。
列表 primes 的顺序：因为每次加入质数是从小到大的，所以遍历 primes 时，p 也是从小到大的，这保证了 i % p == 0 能够及时中断。

5. 完整可运行的示例（含主函数和计时对比）

下面代码展示了如何用线性筛法找出100以内的所有质数，并且加入了简单的计时对比（与埃氏筛法对比运行时间，不过这里只演示线性筛本身）。

import time

def linear_sieve(n):
    """线性筛法：返回 n 以内所有质数的列表"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是质数
    primes = []

    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False
            if i % p == 0:
                break
    return primes

# 主程序
n = 100
prime_list = linear_sieve(n)
print(f"1 到 {n} 之间的质数有：{prime_list}")
print(f"共 {len(prime_list)} 个")

# 额外：展示一下大范围的速度（可选）
n_large = 10_000_000
start = time.time()
large_result = linear_sieve(n_large)
end = time.time()
print(f"线性筛法找出 1 到 10,000,000 内的质数耗时 {end - start:.4f} 秒，共 {len(large_result)} 个质数")

运行结果（示例）：

1 到 100 之间的质数有：[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]
共 25 个
线性筛法找出 1 到 10,000,000 内的质数耗时 0.8724 秒，共 664579 个质数

（实际运行时间因电脑而异，但可以明显感受到线性筛的速度）

6. 相关知识点，你可以继续探索

埃氏筛法：线性筛法的基础，理解它的优缺点才能更好地理解线性筛的好处。
欧拉函数：线性筛法不仅能筛质数，还能在线性时间内计算每个数的欧拉函数（φ(n)），这是数论中的重要函数。
莫比乌斯函数：同样可以通过线性筛法在线性时间内求出。
质因数分解：利用线性筛法预处理的最小质因子，可以快速分解任意合数。
密码学应用：大质数的生成常用筛法，比如RSA加密算法需要随机大质数，线性筛能高效找出候选质数。

如果你对以上内容感兴趣，可以继续学习“线性筛求欧拉函数”、“线性筛求莫比乌斯函数”等进阶主题。记住，线性筛法是处理数论问题时的一把“瑞士军刀”，掌握它会让你的算法工具箱更加充实！