从LeetCode实战出发：当‘计数质数’题数据范围到1e7，为什么你的埃氏筛会超时而欧拉筛稳过？

从LeetCode实战看筛法性能：当数据量突破1e7时如何选择最优算法

在算法竞赛和编程面试中，质数筛选问题看似基础却暗藏玄机。许多开发者都能轻松写出埃拉托斯特尼筛法（埃氏筛）的代码，但当LeetCode题目中的n值从1e5跃升至1e7甚至更高时，原本运行良好的代码突然超时，而改用欧拉筛却能顺利通过。这背后的原因不仅仅是时间复杂度的理论差异，更涉及计算机底层的内存访问模式、缓存命中率等实际问题。

1. 两种筛法的核心差异与性能表现

埃氏筛和欧拉筛虽然都能解决质数筛选问题，但它们的内部机制和性能特征截然不同。理解这些差异是做出正确算法选择的基础。

1.1 埃氏筛的工作机制与性能瓶颈

埃氏筛的基本思路是从2开始，将每个质数的倍数都标记为合数。一个常见的优化是从ii开始标记，而不是从2i开始：

def eratosthenes(n): is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: for j in range(i*i, n+1, i): is_prime[j] = False return [i for i, prime in enumerate(is_prime) if prime]

埃氏筛的主要性能问题：

• 时间复杂度为O(n log log n)，虽然理论复杂度不错，但实际运行时会重复标记许多合数
• 当n增大时，内存访问模式变得不连续，导致缓存命中率下降
• 对于大范围的筛选，外层循环的i*i可能溢出，需要额外处理

1.2 欧拉筛的线性优势

欧拉筛（又称线性筛）通过确保每个合数只被其最小质因数筛除，实现了真正的线性时间复杂度：

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

欧拉筛的关键优化点：

• 每个合数只被标记一次，时间复杂度严格O(n)
• 内存访问模式更连续，对CPU缓存更友好
• 通过if i % p == 0: break这一关键语句避免了重复标记

2. 从理论到实践：当n=1e7时的真实表现

理论分析只能告诉我们算法的大致趋势，实际性能还需要考虑编程语言特性、硬件架构等因素。

2.1 时间复杂度对比实验

下表展示了两种算法在不同规模下的实际运行时间（单位：毫秒）：

从数据可以看出，随着n的增大，埃氏筛的时间增长明显快于欧拉筛。当n=1e8时，埃氏筛已经需要30秒，而欧拉筛仅需9秒。

2.2 内存访问模式的影响

现代CPU的缓存体系对算法性能有重大影响。埃氏筛在处理大范围数据时：

• 内层循环的步长为i，导致内存访问不连续
• 当n很大时，缓存命中率急剧下降，频繁的缓存未命中拖慢速度

相比之下，欧拉筛：

• 内层循环总是遍历已知的质数列表，访问模式更可预测
• 对每个i的处理都集中在连续的内存区域，缓存利用率高

3. 语言特性对筛法实现的影响

不同编程语言对算法的实现也有显著影响，特别是在处理大数组和内存管理方面。

3.1 C++实现要点

在C++中，使用原生数组通常比vector更快：

// 欧拉筛的C++优化实现 const int MAX = 1e8; bool is_prime[MAX+1]; vector<int> primes; void euler_sieve(int n) { memset(is_prime, true, sizeof(is_prime)); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) { if (is_prime[i]) primes.push_back(i); for (int p : primes) { if (i * p > n) break; is_prime[i * p] = false; if (i % p == 0) break; } } }

C++优化技巧：

• 使用位运算压缩存储（每个bool用1位而非1字节）
• 预先分配足够大的数组避免动态扩容
• 使用编译器优化选项（如-O2）

3.2 Python实现的特殊考量

Python的动态类型和列表操作较慢，需要特别优化：

def euler_sieve_py(n): is_prime = bytearray([1]) * (n + 1) is_prime[0] = is_prime[1] = 0 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] = 0 if i % p == 0: break return primes

Python优化建议：

• 使用bytearray代替list节省内存
• 考虑使用NumPy数组进一步提高速度
• 对于极大n值（>1e8），可能需要分段处理

4. 高级优化与替代方案

当数据规模继续增大时，即使是欧拉筛也可能遇到内存限制。这时需要考虑更高级的优化技术。

4.1 分段筛法（Segmented Sieve）

分段筛法将整个范围分成较小的块，逐块筛选，显著减少内存使用：

def segmented_sieve(n, segment_size=10**6): primes = [] if n >= 2: primes.append(2) # 先用普通筛法找出√n以内的质数 limit = int(n**0.5) + 1 base_primes = euler_sieve(limit) # 分段处理 for low in range(3, n + 1, segment_size): high = min(low + segment_size - 1, n) sieve = bytearray([1]) * (high - low + 1) for p in base_primes[1:]: # 跳过2 # 计算第一个能被p整除的数>=low first = max(p * p, ((low + p - 1) // p) * p) for multiple in range(first, high + 1, p): sieve[multiple - low] = 0 # 收集当前段的质数 for i in range(low % 2, high - low + 1, 2): if sieve[i]: primes.append(low + i) return primes

分段筛法的适用场景：

• 当n极大（如1e10以上），无法一次性装入内存
• 需要并行处理时，可以分派不同段给不同线程/进程
• 对内存使用有严格限制的环境

4.2 多线程与GPU加速

对于极端大规模（如n>1e12）的质数筛选，可以考虑：

• 多线程实现：将范围划分为多个区间，每个线程处理一个区间
• GPU加速：利用CUDA等框架，将筛选过程并行化
• 分布式计算：使用多台机器协同计算，如MapReduce模型

5. 实际应用中的选择策略

在LeetCode比赛或技术面试中，如何根据具体问题选择合适的筛法？

选择埃氏筛的情况：

• 问题规模较小（n<1e6）
• 需要快速实现，不追求极致性能
• 内存资源充足，代码简洁性更重要

选择欧拉筛的情况：

• 问题规模较大（n>1e6）
• 需要最优时间复杂度
• 对运行时间有严格要求

选择分段筛的情况：

• 问题规模极大（n>1e8）
• 内存资源有限
• 需要并行处理能力

在实际项目中，我曾遇到一个需要计算1e9以内质数个数的需求。最初使用埃氏筛，运行时间超过1分钟；改用欧拉筛后降至10秒左右；最终采用分段筛结合多线程，将时间进一步压缩到3秒以内。这种性能差异在算法竞赛中往往就是AC与TLE的区别。