Python素数筛选脚本为何在第33178210次迭代后终止执行？

核心问题分析 #

你的程序在处理999999937时突然终止，大概率是内存耗尽被系统强制杀死，其次才是单线程筛选效率过低导致无响应（但你说程序直接终止，OOM的可能性远大于后者）。具体原因：

• 要是用的普通埃氏筛：999999937长度的布尔列表，Python里每个bool都是对象，单元素内存开销就有28字节左右，算下来总内存需求接近27GB，远超你的16GB内存，系统直接触发OOM Killer把进程掐了。
• 要是用逐个调用is_prime判断：单个大整数的素性检测本身就慢得离谱，而且999999937以内的素数有5000多万个，全存列表里的话，光这个列表就能占好几GB内存，同样会把内存撑爆。

排查步骤 #

1. 确认系统杀进程的原因
   • Linux：去/var/log/syslog或者敲dmesg命令，搜Out of memory或者你的进程名，看看是不是系统因为内存不够把程序干掉了。
   • Windows：打开事件查看器，查“Windows日志->系统”里有没有“内存不足”的警告，或者进程被终止的记录。
2. 实时监控内存占用
   • 运行程序的时候开着top（Linux）或者任务管理器（Windows），要是内存占比蹭蹭往100%跑，然后程序直接没了，那肯定是内存问题。
3. 测测is_prime的效率
   • 拿999999937本身（这数是个素数）测一下is_prime的耗时，要是跑个好几分钟都出不来结果，说明单线程逐个检测的效率完全扛不住这么大的区间。

解决方案 #

1. 换成分段筛法（Segmented Sieve） #

这是处理超大区间素数筛选的标准操作，核心就是把大区间拆成一个个小段，只在内存里处理当前小段的素数标记，同时复用小于等于sqrt(999999937)（大概31622）的素数列表。给你个示例代码：

import math

def simple_sieve(limit):
    # 生成小于等于sqrt(上限)的素数表，用于后续分段筛选
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(limit)) + 1):
        if sieve[i]:
            sieve[i*i : limit+1 : i] = [False] * len(sieve[i*i : limit+1 : i])
    return [i for i, is_p in enumerate(sieve) if is_p]

def segmented_sieve(low, high):
    sqrt_high = int(math.sqrt(high))
    base_primes = simple_sieve(sqrt_high)
    segment_size = 10**6  # 分段大小可调，100万的分段大概占1MB内存，适合16GB机器
    primes = []

    for start in range(max(low, 2), high + 1, segment_size):
        end = min(start + segment_size - 1, high)
        # 初始化当前分段的素数标记
        sieve = [True] * (end - start + 1)
        # 用基础素数标记当前分段的非素数
        for p in base_primes:
            first_multiple = max(p*p, ((start + p - 1) // p) * p)
            sieve[first_multiple - start : end - start + 1 : p] = [False] * len(sieve[first_multiple - start : end - start + 1 : p])
        # 收集当前分段的素数
        primes.extend([start + i for i, is_p in enumerate(sieve) if is_p])
    return primes

# 别把所有素数存列表，直接写文件，省内存
with open('large_primes.txt', 'w') as f:
    for prime in segmented_sieve(2, 999999937):
        f.write(f"{prime}\n")

2. 抠内存细节 #

• 绝对别把几百万个素数全存列表里，生成一个就写一个文件，避免内存堆得越来越大。
• 要是必须用数组存标记，用array.array('b')代替普通列表，每个元素只占1字节，比Python原生列表省N倍内存。

3. 优化is_prime（只适合单个素数检测，大区间还是用分段筛） #

如果非要用逐个判断的方式，把is_prime改得高效点：

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w  # 交替加2和4，跳过偶数和3的倍数，减少循环次数
    return True

额外提醒 #

• 别用多线程处理这种CPU密集型任务：Python的GIL会锁死多线程的CPU利用率，改用multiprocessing多进程更靠谱。
• 写文件的时候定期刷缓存：数据量太大的话，隔一段时间调用f.flush()，避免缓存爆了出问题。

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