Python3大整数范围素数生成器内存错误求助

问题根源 #

你遇到的内存错误直接来自第15行primes = [False for i in range(n+1)]：当n超过20亿时，这个列表会包含20亿+1个元素。Python中每个布尔对象在列表里实际占用的内存远不止1字节（小对象的内存开销），算下来至少需要几十GB内存，普通机器根本扛不住。

解决方案 #

1. 用位数组压缩内存占用 #

最直接的优化是把普通列表换成位数组，每个元素只占用1位内存。20亿位仅约250MB，完全在普通机器的内存范围内。

• 第三方库方案（推荐）：使用bitarray库
  先安装：

  pip install bitarray
  

  替换原代码的列表创建部分：

  from bitarray import bitarray
  primes = bitarray(n+1)
  primes.setall(False)  # 初始化为全False
  

  后续的primes[i] == False、primes[j*i] = True等操作和原代码完全一致。

• 标准库方案：用array模块
  如果不想装第三方库，用array.array存储单字节的0/1（0代表False，1代表True），内存占用是位数组的8倍，但依然远小于普通列表：

  import array
  primes = array.array('b', [0]) * (n+1)
  

  注意这里判断素数的逻辑要改成primes[i] == 0，标记合数改成primes[j*i] = 1。

2. 用分段筛法彻底解决超大内存问题 #

如果n大到即使位数组也有点吃力，或者想进一步优化，**分段筛（Segmented Sieve）**是更合适的方案。它不需要一次性创建覆盖整个n范围的数组，而是把范围分成小段，每次只处理一段，内存占用仅和分段大小以及√n以内的素数数量有关（√20亿约44721，完全可以忽略）。

分段筛的核心逻辑：

1. 先找出√n以内的所有素数（用普通埃氏筛即可，内存压力极小）
2. 将n分成多个连续的小段（比如每段100万个数）
3. 对每个小段，用第一步得到的素数标记其中的合数，统计该段内的素数数量，同时检查是否存在和当前段素数相加等于n的素数（对应你代码里的count统计逻辑）

3. 关于yield的正确使用 #

如果想逐个生成素数同时统计数量，可以在生成器里维护一个计数器：

def count_primes_generator(n):
    count = 0
    # 这里用优化后的筛法（比如分段筛）逐个获取素数
    for prime in your_sieve_logic(n):
        count += 1
        yield prime, count

调用时可以直接遍历获取素数和累计计数：

for p, total in count_primes_generator(2324522934):
    print(f"素数：{p}，累计数量：{total}")

针对你代码的快速修改建议 #

先尝试用bitarray替换原列表，这是改动最小的方案，能直接解决内存问题。如果你需要统计的是和为n的素数对数量，后续可以结合分段筛进一步优化运行速度。

内容的提问来源于stack exchange，提问作者sull.ktk