欧拉计划第10题：埃拉托斯特尼筛法实现与运行时间优化问询

我研究欧拉计划第10题好几天了，一直在想办法优化程序运行时间，不想再让它跑半小时甚至一小时。最开始我是逐个判断质数再移除非质数，后来了解到埃拉托斯特尼筛法（Sieve of Eratosthenes），就试着实现了，但不确定这个版本有没有提升性能。

我的实现代码如下：

goal = 2000000
allBelow = [int(x) for x in range(0,goal)]

def sieveOut(lst:list,value:int):
    index = lst.index(value)
    while index < len(lst):
        v=lst[index]
        if v != value and v%value == 0:
            print("REMOVING: " + str(v))
            lst.remove(v)
        index+=value
    return lst

index = 0
allBelowLength = len(allBelow)
while index < allBelowLength:
    value = allBelow[index]
    if value <= 1:
        print("Removing " + str(value))
        allBelow.remove(value)
    else:
        print("Sieving out " + str(value))
        allBelow = sieveOut(allBelow,value)
        index += 1
    allBelowLength = len(allBelow)

print(str(allBelow) + " :: " + str(sum(allBelow)))

你的代码为什么慢？ #

你的实现没发挥出埃氏筛法的真正性能，核心问题有这些：

• 频繁列表删除拖慢速度：list.remove()是O(n)复杂度，每次删除都要遍历整个列表，200万级别的数据量下，这个操作会累积出巨大的耗时
• 冗余的索引查找：lst.index(value)每次都要遍历列表找位置，完全没必要——初始列表是连续的数值，直接用数值本身当索引就行
• 大量打印拖慢IO：每删一个数就打印，IO操作的速度远慢于计算，这会让程序运行时间大幅增加
• 筛法逻辑重复：筛除质数倍数时，从value的位置开始，会重复处理已经被更小质数筛过的数（比如6会被2和3各处理一次）

优化后的埃氏筛法实现 #

goal = 2000000
# 用布尔数组标记质数，初始全为True，0和1直接设为非质数
is_prime = [True] * goal
is_prime[0], is_prime[1] = False, False

# 只遍历到目标数的平方根即可，超过的数若为合数必然有更小的因子
for value in range(2, int(goal ** 0.5) + 1):
    if is_prime[value]:
        # 从value的平方开始标记倍数，更小的倍数已经被之前的质数处理过了
        is_prime[value*value : goal : value] = [False] * len(is_prime[value*value : goal : value])

# 计算所有质数的和
prime_sum = sum(i for i, is_p in enumerate(is_prime) if is_p)
print(prime_sum)

优化点说明 #

• 用标记替代删除：布尔数组的标记操作是O(1)，完全避免了列表删除的高复杂度
• 减少循环范围：遍历到目标数的平方根，大幅减少循环次数
• 避免重复标记：从value*value开始标记倍数，跳过已经被小质数处理过的数
• 移除所有打印：彻底去掉IO操作的耗时

内容的提问来源于stack exchange，提问作者Islarf