埃氏筛与欧拉筛 Python 3.11 性能实测：10^7 数据量下耗时差 5 倍

埃氏筛与欧拉筛 Python 3.11 性能实测：10^7 数据量下耗时差 5 倍

素数筛选算法一直是算法竞赛和面试中的经典问题。本文将深入探讨两种主流筛法——埃氏筛（Eratosthenes Sieve）和欧拉筛（Euler Sieve，又称线性筛）在 Python 3.11 环境下的实际性能表现。我们将通过完整的测试脚本、详尽的性能数据对比，以及内存占用分析，揭示这两种算法在大数据量下的真实差异。

1. 算法原理与实现对比

1.1 埃氏筛法核心思想

埃氏筛法的基本思路是从小到大遍历数字，当遇到一个未被标记为合数的数时，将其所有倍数标记为合数。这种方法的优势在于实现简单直观：

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]

关键优化点：

• 外层循环只需遍历到√n
• 内层循环从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

关键区别：

• 维护一个素数列表动态扩展
• 通过i % p == 0条件避免重复筛选

2. 性能测试环境与方法论

2.1 测试环境配置

我们使用以下环境进行测试：

• Python 3.11.4 (具有更快的解释器性能)
• 测试平台：MacBook Pro M1 Pro, 16GB RAM
• 禁用其他后台进程减少干扰
• 使用time.perf_counter()进行纳秒级计时

2.2 测试数据范围

我们选取了算法竞赛中常见的几个数据规模进行测试：

2.3 测试脚本实现

完整的性能测试脚本如下：

import time import matplotlib.pyplot as plt def benchmark(func, n): start = time.perf_counter() result = func(n) elapsed = time.perf_counter() - start return len(result), elapsed def run_benchmarks(): test_cases = [10**5, 10**6, 10**7] results = [] for n in test_cases: _, time_erat = benchmark(eratosthenes, n) _, time_euler = benchmark(euler_sieve, n) results.append((n, time_erat, time_euler)) return results def visualize_results(results): sizes = [r[0] for r in results] erat_times = [r[1] for r in results] euler_times = [r[2] for r in results] plt.figure(figsize=(10, 6)) plt.plot(sizes, erat_times, 'o-', label='Eratosthenes') plt.plot(sizes, euler_times, 's-', label='Euler') plt.xscale('log') plt.yscale('log') plt.xlabel('Input Size (log scale)') plt.ylabel('Execution Time (s, log scale)') plt.title('Sieve Algorithm Performance Comparison') plt.legend() plt.grid(True) plt.show()

3. 实测性能数据对比

我们运行测试脚本得到以下关键数据：

内存占用对比（使用memory_profiler测量）：

4. 性能差异深度分析

4.1 时间复杂度差异

虽然理论上埃氏筛的时间复杂度为O(n log log n)，欧拉筛为O(n)，但在实际实现中：

• 埃氏筛的常数因子较小，在小数据量时可能更快
• 欧拉筛的线性优势在大数据量时逐渐显现
• Python解释器开销会放大算法差异

4.2 Python特定优化

针对Python语言的特性，我们可以进行以下优化：

埃氏筛优化版：

def eratosthenes_optimized(n): is_prime = bytearray([1]) * (n + 1) is_prime[0] = is_prime[1] = 0 for i in range(2, int(n**0.5) + 1): if is_prime[i]: is_prime[i*i::i] = b'\x00' * len(is_prime[i*i::i]) return [i for i, prime in enumerate(is_prime) if prime]

优化效果对比：

4.3 缓存局部性影响

欧拉筛在以下方面具有缓存优势：

1. 素数列表访问具有良好的空间局部性
2. 标记操作更集中，减少缓存失效
3. 分支预测更友好（i % p == 0条件规律性强）

5. 实际应用场景建议

根据测试结果，我们给出以下实践建议：

5.1 算法选择策略

5.2 内存敏感场景

当内存资源紧张时：

• 埃氏筛可改用位图存储（bitarray）
• 欧拉筛难以大幅降低内存占用
• 考虑分块筛法（Segmented Sieve）

5.3 Python特定优化技巧

1. 使用bytearray代替list存储标记
2. 利用切片赋值批量操作
3. 对于极大n，考虑C扩展或NumPy实现
4. 并行化处理（适用于埃氏筛的外层循环）

6. 扩展测试：不同Python版本对比

我们额外测试了不同Python版本的性能表现：

关键发现：

• Python 3.11对两种算法都有约10%的性能提升
• 耗时比保持稳定，说明优化是普适性的