优化埃拉托斯特尼筛法：解决大跨度素数查找的内存错误

现有代码仅能处理百万级数值范围，实际需支持1亿到10亿甚至万亿级的素数查找。当设置范围为1到10亿时，持续出现内存错误，需对以下代码进行优化：

import time
from math import isqrt


def sieveprmcheck(n):
    if n < 2:
        return []
    prime_num = [True] * (n + 1)
    prime_num[0] = False
    prime_num[1] = False

    for i in range(2, isqrt(n) + 1):
        if prime_num[i]:
            for k in range(i * i, n + 1, i):
                prime_num[k] = False

    primes = [i for i in range(n + 1) if prime_num[i]]
    return primes


def segsieve():
    primes = sieveprmcheck(n)

    prime = [True] * (n - m + 1)

    for i in primes:
        lower = (m // i)

        if lower <= 1:
            lower = i + i
        elif (m % i) != 0:
            lower = (lower * i) + i
        else:
            lower = lower * i
        for j in range(lower, n + 1, i):
            prime[j - m] = False

    prime_numbers = []
    for k in range(m, n + 1):
        if prime[k - m]:
            prime_numbers.append(k)

    return prime_numbers


def palcheck(primes):
    special_numbers = set()
    for num in primes:
        if str(num) == str(num)[::-1]:  # Check if the number is a palindrome
            special_numbers.add(num)

    special_numbers_list = sorted(list(special_numbers))
    print('Number of Special Numbers:', len(special_numbers_list), ':',
          special_numbers_list[:3] + special_numbers_list[-3:])
    return special_numbers_list


if __name__ == '__main__':
    m = int(input('Please enter starting number: '))
    n = int(input('Please enter ending number: '))
    start = time.time()
    primes = segsieve()
    Special_Num = palcheck(primes)
    end = time.time()

    time_spent = end - start
    print("\nTime spent:", time_spent, "seconds")

1. 修复分段筛核心逻辑错误 #

原segsieve函数调用sieveprmcheck(n)会生成整个n范围的素数，这是大n下内存爆炸的核心原因。分段筛仅需生成√n以内的素数即可，修改调用参数：

primes = sieveprmcheck(isqrt(n))

2. 用比特数组压缩内存占用 #

Python中布尔列表每个元素占1字节，改用比特数组可将内存占用降至1/8。可使用bitarray第三方库：

from bitarray import bitarray

# 替换原布尔列表初始化
prime = bitarray(n - m + 1)
prime.setall(True)

若依赖受限，可手动用bytearray模拟比特位存储，进一步节省内存。

3. 简化区间标记逻辑 #

原代码计算lower的分支可简化为直接计算区间内第一个i的倍数：

start = max(i*i, ((m + i - 1) // i) * i)
for j in range(start, n + 1, i):
    prime[j - m] = False

此写法更简洁高效，避免冗余分支判断。

4. 边筛边检查回文，减少内存存储 #

无需存储所有素数，可在分段筛过程中直接检查当前区间内的素数是否为回文，符合条件则立即记录，避免大量素数占用内存。

5. 拆分超大区间处理 #

针对万亿级范围，将大区间拆分为多个小分段（如100万/段），逐个处理后释放内存，避免单区间内存过载。

6. 优化回文数检查逻辑 #

替换字符串转换的回文判断，改用数学方法提升效率：

def is_palindrome(num):
    original = num
    reversed_num = 0
    while num > 0:
        reversed_num = reversed_num * 10 + num % 10
        num = num // 10
    return original == reversed_num

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