欧拉计划第10题优化求助：两百万以内质数和计算提速方案

原代码的核心问题 #

• 未遵循埃拉托斯特尼筛法的核心优化逻辑：从质数的平方开始标记倍数，而是遍历整个数组检查每个元素，做了大量重复操作。
• 冗余的tempSieve判断逻辑，不仅无实际作用，还频繁复制数组，大幅拖慢运行速度。
• 浪费了numpy的向量化优势，用Python循环遍历数组元素，完全没发挥numpy的性能特性。

优化后的实现 #

方案1：基于numpy的高效筛法 #

利用numpy的布尔数组和切片操作批量标记非质数，避免Python层面的循环开销：

import numpy as np

def sieve_prime(n):
    if n <= 2:
        return 0
    # 初始化布尔数组，索引对应数值，初始全为True
    is_prime = np.ones(n, dtype=bool)
    # 0和1不是质数
    is_prime[0] = is_prime[1] = False
    # 遍历到上限的平方根即可
    for i in range(2, int(np.sqrt(n)) + 1):
        if is_prime[i]:
            # 从i的平方开始，以i为步长批量标记非质数
            is_prime[i*i : n : i] = False
    # 筛选所有质数并求和
    return np.sum(np.arange(n)[is_prime])

print(sieve_prime(2000000))

方案2：纯Python高效筛法 #

如果不想依赖numpy，纯Python的列表切片实现同样能达到极快的速度：

def sieve_prime(n):
    if n <= 2:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    # 遍历到上限的平方根
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            # 批量标记i的倍数为非质数
            is_prime[i*i : n : i] = [False] * len(is_prime[i*i : n : i])
    # 求和所有质数
    return sum(i for i, val in enumerate(is_prime) if val)

print(sieve_prime(2000000))

优化点说明 #

1. 从质数平方开始标记：避免重复标记已被更小质数处理过的倍数，减少一半以上的操作量。
2. 布尔数组替代数值数组：布尔值占用内存远小于整数，且标记操作更高效。
3. 批量操作替代循环遍历：用numpy切片或Python列表切片一次性处理所有倍数，避免Python循环的性能瓶颈。
4. 移除冗余逻辑：删除原代码中无用的tempSieve相关操作，简化逻辑的同时提升速度。

这两个优化后的版本处理200万以内的质数求和，耗时都在毫秒级，远快于原代码的数分钟。

内容的提问来源于stack exchange，提问作者Daniel T. McGuiness