1、埃氏筛的重复标记问题
在上一篇中，我们学习了埃氏筛（埃拉托斯特尼筛法）。
埃氏筛非常高效，但它有一个小痛点：
举个例子，假设我们筛选 2 到 30：
这说明埃氏筛在“标记合数”这件事上，会有一些重复劳动。
当范围更大时，这些重复操作会越来越多，影响效率。
欧拉筛（线性筛）的核心目标就是：
2、欧拉筛如何实现不重复标记
★核心原理是：所有合数都可唯一表示为「最小质因子 × 另一个整数」，仅用最小质因子做一次标记，从根源上消除埃氏筛的重复标记问题
比如 30 的最小质数是 2，可以表示为 。 当我们处理到 15 时，通过 2 去标记 30 为合数。
同样比如 18 的最小质数是 2，可以表示为 。 当我们处理到 9 时，通过 2 去标记 18 为合数。
同样比如 15 的最小质数是 3，可以表示为 。 当我们处理到 5 时，通过 3 去标记 15 为合数。
按照这样的规律来保证每个合数只会被它的最小质数去标记一次。
为了实现这样的机制，我们设计这样的处理过程：
从2开始逐一筛选每一个数i：
- 如果
i没有被划掉，说明它是质数，我们把它加入质数列表primes。
2.1 i的第一种情况(质数)：
我们把小于等于i的质数列表primes中的每个质数p去标记合数：
- 如果
i * p > n，就停止标记（因为超出范围了） - 关键：如果
i % p == 0，说明p已经是i的最小质因数了，那么后续更大的质数就不再参与i的生成过程了，避免了重复标记。
比如当前的i时7, 当前的质数列表primes是[2, 3, 5,7]：
- 我们用
2去标记7 * 2 = 14，14标记为合数，标记一次 - 我们用
3去标记7 * 3 = 21，21标记为合数，标记一次 - 我们用
5去标记7 * 5 = 35， 35标记为合数，标记一次 - 我们用
7去标记7 * 7 = 49，49标记为合数，标记一次 - 处理完成后，
7 % 7 == 0，说明7已经是7的最小质因数了，后面就不需要处理了。
2.2 i的第二种情况(合数)：
如果当前数 i 已经被划掉了，说明它是合数，我们不把它加入质数列表 primes。 但是我们仍然用 primes 中的每个质数 p 去标记合数：
- 如果
i * p > n，就停止标记（因为超出范围了） - 关键：如果
i % p == 0，说明 p 已经是 i 的最小质因数了，那么后续更大的质数就不再参与 i 的生成过程了，避免了重复标记。
比如当前的i时9, 当前的质数列表primes是[2, 3, 5,7]：
- 我们用
2去标记9 * 2 = 18，18标记为合数，标记一次 - 我们用
3去标记9 * 3 = 27，27标记为合数，标记一次 - 处理完成后，
9 % 3 == 0，说明3已经是9的最小质因数了，后面就不需要处理了。
通过这样的机制，我们保证了每个合数只会被它的最小质数去标记一次，从而避免了重复标记的问题。
3、欧拉筛的算法设计
我们把问题定义为：找出 2 到 n 的全部质数。
算法步骤如下：
- 建立布尔数组
is_prime，初始都设为 True - 如果
is_prime[i] 仍为 True，说明 i 是质数，加入 primes - 标记
is_prime[i * p] = False
这个算法被称为“线性筛”，因为它的时间复杂度接近线性级别。
4、欧拉筛的数学建模
4.1 输入与输出
4.2 变量与状态
is_prime[x]：布尔值，表示 x 当前是否被判定为质数
4.3 约束关系
对于当前 i 与质数 p：
若 composite <= n，则该数一定是合数，需要标记。
并且使用停止条件：
其含义是：当 p 已经是 i 的最小质因数时，后续更大的质数不再参与当前 i 的生成过程，从而避免重复标记。
5、Python 代码实现
下面这版代码按初级学习者编写，注释尽量写清楚“每一步在做什么”。
defeuler_sieve(n):
"""
欧拉筛（线性筛）：返回 2 到 n 的所有质数
"""
# 如果 n 小于 2，就没有质数
if n < 2:
return []
# is_prime[x] 表示 x 当前是否是质数
# 先假设 0..n 全是质数，后面再把合数改成 False
is_prime = [True] * (n + 1)
# 0 和 1 不是质数
is_prime[0] = False
is_prime[1] = False
# 用来存放已经找到的质数
primes = []
# i 从 2 开始遍历到 n
for i in range(2, n + 1):
# 如果 i 还没有被标记为合数，说明 i 是质数
if is_prime[i]:
primes.append(i)
# 用“已知质数列表”去生成并标记合数
for p in primes:
# i * p 超出范围就不用继续了
if i * p > n:
break
# i * p 一定是合数，标记为 False
is_prime[i * p] = False
# 关键：如果 p 是 i 的最小质因数，就立刻停止
# 这样可以保证每个合数只被标记一次
if i % p == 0:
break
return primes
# ===== 主程序：测试筛到 1000 =====
n = 1000
prime_list = euler_sieve(n)
print(f"2 到 {n} 之间一共有 {len(prime_list)} 个质数")
print("这些质数是：")
print(prime_list)
示例输出（部分）：
2 到 1000 之间一共有 168 个质数
这些质数是：
[2, 3, 5, 7, 11, 13, ... , 983, 991, 997]
6、同样筛选1000个质数，埃氏筛和欧拉筛的性能对比
为了公平，我们统一比较“筛选 2..1000 的质数”。
下面代码统计两种筛法的：
import time
deferatosthenes_sieve(n):
"""埃氏筛：返回质数列表和标记次数"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
mark_count = 0
p = 2
while p * p <= n:
if is_prime[p]:
# 从 p*p 开始标记是埃氏筛常见优化
multiple = p * p
while multiple <= n:
# 统计一次“标记动作”
mark_count += 1
is_prime[multiple] = False
multiple += p
p += 1
primes = [x for x in range(2, n + 1) if is_prime[x]]
return primes, mark_count
defeuler_sieve_with_count(n):
"""欧拉筛：返回质数列表和标记次数"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
primes = []
mark_count = 0
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
mark_count += 1
is_prime[i * p] = False
if i % p == 0:
break
return primes, mark_count
n = 1000
# 测埃氏筛
start = time.perf_counter()
primes_e, marks_e = eratosthenes_sieve(n)
time_e = time.perf_counter() - start
# 测欧拉筛
start = time.perf_counter()
primes_l, marks_l = euler_sieve_with_count(n)
time_l = time.perf_counter() - start
print("是否得到同样的质数结果：", primes_e == primes_l)
print(f"埃氏筛：质数个数={len(primes_e)}, 标记次数={marks_e}, 用时={time_e:.6f}秒")
print(f"欧拉筛：质数个数={len(primes_l)}, 标记次数={marks_l}, 用时={time_l:.6f}秒")
运行的结果如下：
是否得到同样的质数结果： True
埃氏筛：质数个数=168, 标记次数=1411, 用时=0.000137秒
欧拉筛：质数个数=168, 标记次数=831, 用时=0.000177秒
你通常会看到下面的现象：
复杂度对比：
小结：
- 欧拉筛通过“最小质因数 + 提前停止”避免重复标记，效率更高
10个月宝宝每天需要喝多少奶粉？
