如何优化Python中梅森素数筛的运行速度？

嘿，我帮你分析下你的梅森素数筛为啥到11213就变慢了，再给你几个实用的优化方案：

首先，咱们先拆解下现有代码的性能瓶颈：

1. 素数生成器的冗余与递归开销：你实现了两个几乎一样的生成器postponed_sieve()和prime_sieve()，而且postponed_sieve()还递归调用自己，这会带来额外的生成器上下文切换开销，素数越大，这个损耗越明显。
2. mod_mersenne的循环效率低：当前的循环是逐位移位处理大整数，当prime到11213时，2^11213-1是个超级大的数，循环次数会剧增。
3. 函数调用的累积开销：is_mersenne_prime里每次循环都调用mod_mersenne，上万次循环下来，函数调用的开销会被放大很多。
4. 筛法的字典操作损耗：原筛法用字典存储合数，当数据量变大时，哈希查找和删除的开销会逐渐增加。

接下来是针对性的优化方案：

方案一：简化素数生成器，去掉递归冗余 #

把重复的生成器合并成一个非递归的版本，减少生成器嵌套的开销：

def optimized_prime_sieve():
    yield 2
    sieve = {}
    candidate = 3
    while True:
        if candidate not in sieve:
            yield candidate
            # 记录当前素数的平方作为第一个需要标记的合数
            sieve[candidate * candidate] = [candidate]
        else:
            # 把当前合数的所有素因子对应的下一个合数加入筛子
            for p in sieve[candidate]:
                sieve.setdefault(p + candidate, []).append(p)
            del sieve[candidate]
        candidate += 2

方案二：优化mod_mersenne的取模逻辑 #

利用梅森数的数学性质：n mod (2^p-1)等价于把n的二进制按p位分组求和后再取模，这样能大幅减少循环次数：

def mod_mersenne(n, prime):
    mersenne = (1 << prime) - 1
    total = 0
    while n > 0:
        # 每次取prime位的数值累加
        total += n & mersenne
        n >>= prime
        # 提前处理溢出，避免后续循环过多
        if total > mersenne:
            total = (total & mersenne) + (total >> prime)
    return 0 if total == mersenne else total % mersenne

方案三：内联函数逻辑，减少调用开销 #

把mod_mersenne的逻辑直接写到is_mersenne_prime里，避免上万次的函数调用损耗，还能提前终止循环：

def is_mersenne_prime(prime):
    if prime == 2:
        return True
    mersenne = (1 << prime) - 1
    s = 4
    remaining = prime - 2
    while remaining > 0:
        s_sq = s * s - 2
        # 内联取模逻辑
        total = s_sq
        while total > mersenne:
            total = (total & mersenne) + (total >> prime)
        s = 0 if total == mersenne else total
        # 提前终止，已经满足条件就不用继续循环了
        if s == 0:
            break
        remaining -= 1
    return s == 0

方案四：并行化检验（进阶优化） #

梅森素数的检验是独立的任务，可以用多进程把素数分配到不同CPU核心并行处理，比如用multiprocessing模块：

from multiprocessing import Pool

def check_mersenne(prime):
    if is_mersenne_prime(prime):
        return prime
    return None

def calculate_perfects():
    yield 2
    primes = optimized_prime_sieve()
    next(primes)
    # 按CPU核心数创建进程池
    with Pool() as pool:
        # 批量提交素数检验任务
        for result in pool.imap_unordered(check_mersenne, primes):
            if result is not None:
                yield result
                print(f"Found Mersenne prime exponent: {result}")

额外建议 #

如果你的场景允许使用第三方库，强烈推荐gmpy2——它对大整数运算和卢卡斯-莱默检验做了底层优化，速度会比纯Python快几十甚至上百倍，处理11213这种级别的指数会轻松很多。

内容的提问来源于stack exchange，提问作者Tom E. O'Neil