Python 赋能数学学习 9:欧拉筛如何解决埃氏筛重复标记痛点

1、埃氏筛的重复标记问题

在上一篇中，我们学习了埃氏筛（埃拉托斯特尼筛法）。

埃氏筛非常高效，但它有一个小痛点：

• 同一个合数，可能会被多个质数重复标记

举个例子，假设我们筛选 2 到 30：

• 用 2 去标记时，12 会被标记一次
• 用 3 去标记时，12 又会被标记一次
• 同理，18、24、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为合数
• 如果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 为合数
• 如果 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 的全部质数。

算法步骤如下：

1. 建立布尔数组 is_prime，初始都设为 True
2. 从 2 遍历到 n
3. 如果 is_prime[i] 仍为 True，说明 i 是质数，加入 primes
4. 遍历 primes 中每个质数 p：
• 若 i * p > n，停止
• 标记 is_prime[i * p] = False
• 若 i % p == 0，停止（避免重复标记）
5. 遍历结束后，primes 就是全部质数

这个算法被称为“线性筛”，因为它的时间复杂度接近线性级别。

4、欧拉筛的数学建模

4.1 输入与输出

• 输入：一个正整数 n
• 输出：区间 2..n 内所有质数

4.2 变量与状态

• is_prime[x]：布尔值，表示 x 当前是否被判定为质数
• primes：按从小到大保存已经找到的质数

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秒

你通常会看到下面的现象：

• 两种方法得到的质数结果完全一致
• 欧拉筛的标记次数更少（每个合数只标记一次）
• 在更大范围下，欧拉筛优势会更明显

复杂度对比：

• 埃氏筛：
• 欧拉筛：

小结：

• 埃氏筛思想直观，适合入门
• 欧拉筛通过“最小质因数 + 提前停止”避免重复标记，效率更高