Python如何实现无递归深度限制的素数惰性计算算法

解决方案 #

你遇到的递归深度超限问题根源是原sieve函数的递归调用次数和已找到的素数数量完全绑定，素数越多递归层数越深，自然会撞到Python的递归深度上限。我们可以在完全保留惰性计算特性、贴合原算法筛选逻辑的前提下，将递归改为迭代实现：

非递归惰性素数筛实现

首先保留你已经改好的非递归自然数生成器：

def nats(n):
    while True:
        yield n
        n += 1

改写后的非递归sieve函数如下：

def sieve():
    # 初始候选流为从2开始的所有自然数
    candidate_stream = nats(2)
    while True:
        current_prime = next(candidate_stream)
        yield current_prime
        # 给候选流新增一层过滤规则：滤除当前素数的倍数，完全等价原递归的参数传递逻辑
        candidate_stream = (i for i in candidate_stream if i % current_prime != 0)

逻辑说明

这个实现和原递归算法的逻辑完全一致：原代码每找到一个素数就递归调用sieve传入过滤后的候选流，迭代版本只是把递归调用替换为循环内更新候选流，没有任何函数递归压栈操作，完全规避了递归深度限制。同时所有过滤规则都是惰性生效的，只有你调用next()取下一个素数时才会执行对应的校验计算，不会预生成大量数据，符合惰性计算的要求。

使用示例

p = sieve()
# 连续取前20000个素数也不会触发递归报错
for _ in range(20000):
    print(next(p))

如果追求更高的计算效率，也可以选择维护已发现素数列表、校验到平方根的优化实现，同样是惰性非递归的：

import math

def sieve_optimized():
    primes = []
    for num in nats(2):
        is_prime = True
        sqrt_num = math.isqrt(num)
        for p in primes:
            if p > sqrt_num:
                break
            if num % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
            yield num

这个版本避免了生成器多层嵌套，计算大素数时的性能会更好，同样没有递归深度问题。

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