欧拉筛（线性筛）算法详解：3 个关键步骤与 2 个核心证明

欧拉筛（线性筛）算法详解：3 个关键步骤与 2 个核心证明

在算法竞赛和编程面试中，素数筛选是一个经典问题。欧拉筛（又称线性筛）以其**O(n)**的时间复杂度成为最优解方案。本文将彻底拆解这一算法的设计思想，通过三个关键步骤和两个数学证明，让你不仅掌握代码实现，更能理解其背后的数学原理。

1. 算法背景与核心思想

传统筛法（如埃氏筛）存在一个明显缺陷：某些合数会被多次标记。例如数字12，在筛选2的倍数时被标记一次，在筛选3的倍数时又被重复标记。这种重复操作导致埃氏筛的时间复杂度为O(n log log n)。

欧拉筛的突破性在于它确保每个合数只被其最小质因数筛除一次。这一特性通过以下设计实现：

1. 双重循环结构：外层循环遍历每个数i，内层循环遍历已知质数prime[j]
2. 提前终止机制：当i能被prime[j]整除时立即终止内层循环
3. 动态维护质数表：实时更新当前发现的质数集合

def euler_sieve(n): is_prime = [True] * (n+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

2. 三个关键操作步骤解析

2.1 质数收集阶段

当遍历到数字i时，若is_prime[i]仍为True，说明i未被任何小于它的数筛除，因此i必为质数。此时将i加入质数列表primes中。

注意：这个判断必须放在内层循环之前，确保新发现的质数能立即参与后续筛选

2.2 合数标记阶段

对于当前数字i和每个已知质数p，标记i*p为合数。这里存在两个关键优化：

1. 范围控制：当i*p超过n时立即终止循环
2. 标记顺序：总是用较小的质数先进行标记

2.3 提前终止条件

当发现i能被p整除时（即i % p == 0），立即终止内层循环。这是保证线性时间复杂度的关键，其数学原理将在第4节详细证明。

3. 算法正确性的两个核心证明

3.1 命题一：每个合数都会被筛除

对于任意合数x，设其最小质因数为p，则存在k = x/p。由于p是最小质因数，必有k ≥ p。算法在遍历到i = k时：

1. 质数p已在primes列表中（因p ≤ k）
2. 内层循环处理p时，会标记i*p = x为合数
3. 在i=k的循环中，x必定被标记

反例验证：假设不采用最小质因数筛选，如数字45=3×15。若允许用5筛选，当i=9时标记45，但此时9%3==0会提前终止，导致45被3在i=15时标记。

3.2 命题二：每个合数只被筛一次

关键在于理解为何当i % p == 0时需要终止。设i = k*p，则对于下一个质数q > p：

• 本应标记iq = kp*q
• 但这个数会在i' = k*q时被p标记（因为p < q）
• 因此当前循环无需继续

数学表达：

i × q = (k × p) × q = (k × q) × p = i' × p (其中i' = k × q > i)

4. 复杂度分析与实际应用

4.1 时间复杂度证明

每个合数仅被标记一次，每个i都经历常数次操作，因此总操作次数为：

• 质数判断：O(n)
• 合数标记：O(n)（因为n以内合数约n/ln n个，每个标记一次）

总复杂度为严格的O(n)，优于埃氏筛的O(n log log n)。

4.2 空间复杂度

需要两个主要数据结构：

1. 大小为n的布尔数组is_prime → O(n)
2. 质数列表primes（存储π(n)≈n/ln n个质数） → O(n/ln n)

总空间复杂度仍为O(n)。

4.3 性能对比测试

下表展示不同算法在n=1e6时的实际表现：

虽然欧拉筛内存占用略高，但在大规模数据时时间优势明显。当n=1e7时，欧拉筛仍能在300ms内完成，而埃氏筛需要约500ms。

5. 算法变形与扩展应用

欧拉筛不仅能筛选素数，还可扩展用于计算数论函数：

5.1 最小质因数记录

修改算法，记录每个数的最小质因数：

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

5.2 欧拉函数计算

利用线性筛可在O(n)时间内计算1~n的欧拉函数值：

phi = [0]*(n+1) phi[1] = 1 for i in range(2, n+1): if not phi[i]: primes.append(i) phi[i] = i-1 for p in primes: if i*p > n: break if i % p == 0: phi[i*p] = phi[i]*p break else: phi[i*p] = phi[i]*(p-1)

掌握欧拉筛的核心在于理解其"最小质因数筛选"原则。这种思想不仅适用于素数筛选，还可推广到其他数论问题的优化解决方案中。