如何在Python中加速质数计算算法？代码在n=10000时运行异常

先来说说你的代码为啥在n=10000时会出问题——核心原因是效率太低：

• 你用列表prime存储所有候选数，每次remove(i*j)都要遍历整个列表找元素，这是O(n)的操作，n越大越慢；
• 内层循环从2开始遍历，会重复检查已经被筛掉的数（比如i=3时还会去检查6，但6已经被i=2筛掉了），做了大量无用功。

下面给你两种优化方案，还会解答你关于生成器的疑问~

一、标准埃氏筛优化（最快最常用） #

埃拉托斯特尼筛法的正确打开方式是用布尔标记数组，而不是反复修改列表。标记操作是O(1)，而且能避免重复工作：

import math

n = 10000
# 初始化布尔数组，默认所有数都是素数
is_prime = [True] * (n + 1)
# 0和1不是素数，直接标记为False
is_prime[0] = is_prime[1] = False

# 遍历到sqrt(n)即可，因为更大的数的因子已经被更小的素数处理过了
for i in range(2, int(math.isqrt(n)) + 1):
    if is_prime[i]:  # 如果当前数是素数，就标记它的所有倍数为非素数
        # 从i*i开始标记（更小的倍数已经被之前的素数标记过了），步长为i
        is_prime[i*i : n+1 : i] = [False] * len(is_prime[i*i : n+1 : i])

# 收集所有标记为True的数，就是素数列表
primes = [i for i, is_p in enumerate(is_prime) if is_p]
print(primes)

为什么这个版本更快？ #

1. 布尔数组标记：替代了原代码中O(n)的remove操作，标记一个数只需要O(1)时间；
2. 避免重复标记：从i*i开始标记倍数，比如i=5时，10、15已经被2、3标记过了，直接从25开始就行；
3. 切片赋值优化：用切片批量赋值是Python底层C实现的操作，比自己写循环逐个标记快很多。

二、是否需要用生成器？ #

如果你的n特别大（比如超过100万），或者不需要一次性存储所有素数，生成器是个好选择——它能节省内存，按需生成素数，而不是把所有素数都存在列表里。

给你写个生成器版本的埃氏筛：

import math

def sieve_generator(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            is_prime[i*i : n+1 : i] = [False] * len(is_prime[i*i : n+1 : i])
    # 逐个生成素数
    for num, is_p in enumerate(is_prime):
        if is_p:
            yield num

# 使用示例：遍历生成器获取素数
for prime in sieve_generator(10000):
    print(prime, end=' ')

这个版本和上面的标准筛法效率差不多，但内存占用更低——如果n=1e6，标准版本需要存储1e6+1个布尔值（约1MB，其实也不大），但如果n=1e8，生成器的内存优势就很明显了。

小补充：原代码的其他小问题 #

• 初始列表可以直接写成prime = list(range(2, n))，比列表推导式[prime.append(i) for i in range(2,n)]更简洁；
• 用for i in range(2, int(math.isqrt(n)) +1)替代while循环，代码更易读。

内容的提问来源于stack exchange，提问作者Umut TEKİN