Python更快素数计数：解决n≤10^10时执行超时问题求助

你的代码用了针对6k±1形式数的优化筛法，但在n=1e10时超时，核心问题有两个：

• 内存过载：n=1e10时，sieve数组的大小约为3.3e9个bool元素，占用3GB以上内存，数组的创建、切片赋值等操作会因为内存带宽限制变得极慢。
• Python循环开销：外层for循环在Python中执行，即使仅3万多次迭代，加上每次的numpy切片操作，累积时间很容易超过12秒限制。

解决这个问题的最优方案是分段筛法（Segmented Sieve），它通过将大区间拆分成小块处理，大幅降低内存占用，同时避免大数组的低效操作。

分段筛实现思路 #

1. 先计算出≤√n的所有素数（√1e10=1e5，这个范围很小，用普通筛法瞬间完成）。
2. 将[2, n]拆分成多个连续的小分段（比如每段1e6个数字，可根据内存调整）。
3. 对每个分段，用第一步得到的素数标记其中的合数，统计分段内的素数数量，最后累加得到总数。

优化后的代码 #

import math

def count_primes_less_than(n):
    if n < 2:
        return 0
    if n == 2:
        return 1
    if n == 3:
        return 2
    
    # 生成所有<=sqrt(n)的素数
    sqrt_n = int(math.isqrt(n))
    sieve_small = [True] * (sqrt_n + 1)
    sieve_small[0] = sieve_small[1] = False
    for i in range(2, int(math.isqrt(sqrt_n)) + 1):
        if sieve_small[i]:
            sieve_small[i*i : sqrt_n+1 : i] = [False]*len(sieve_small[i*i : sqrt_n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve_small) if is_prime]
    
    count = len(primes)
    # 分段处理大于sqrt(n)的区间
    segment_size = 10**6  # 可根据内存调整，1e6的段仅占约1MB内存
    low = sqrt_n + 1
    high = min(low + segment_size - 1, n)
    
    while low <= n:
        # 初始化分段筛，默认所有数为素数
        segment = bytearray([1])*(high - low + 1)
        for p in primes:
            # 找到分段中p的第一个倍数
            start = max(p*p, ((low + p - 1) // p) * p)
            # 标记该分段内p的所有倍数为合数
            offset = start - low
            segment[offset : high - low + 1 : p] = b'\x00'*len(segment[offset : high - low + 1 : p])
        # 统计分段内的素数数量
        count += sum(segment)
        # 移动到下一个分段
        low = high + 1
        high = min(low + segment_size - 1, n)
    
    return count

代码优势 #

• 内存占用极低：分段大小设为1e6时，每个分段仅占用1MB内存，远小于原代码的3GB。
• 效率更高：Python循环次数大幅减少，且分段内的标记操作使用bytearray的切片赋值，比numpy大数组操作更快。
• 可扩展性强：即使n到1e12也能高效处理，只需调整分段大小即可。

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