欧拉计划第27题：如何用一维列表替换二维列表优化Python代码

我已写出欧拉计划第27题的Python解决方案，能得到正确结果-59231，但运行速度极慢（耗时1765秒）。为提速，我希望将庞大的二维列表box替换为一维列表，请问该如何实现？

问题详情 #

欧拉计划第27题：
欧拉发现了著名的二次公式：$n^2 + n + 41$，对于n从0到39的连续整数，能生成40个素数。但当n=40时，结果能被41整除；n=41时，结果显然也能被41整除。

另一个公式$n^2 -79n +1601$，对于n从0到79的连续整数，生成了80个素数，其系数-79和1601的乘积为-126479。

考虑形式为$n^2 + an + b$的二次公式，其中$|a| < 1000$且$|b| ≤ 1000$（$|n|$表示n的绝对值）。找出能从n=0开始生成最多连续素数的系数a和b，求它们的乘积。

原始代码 #

import time
from sympy import isprime

start_time = time.time()

a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0
b_upper_limit = 1001
a1 = abs(a_lower_limit)
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit

# 存储各a、b组合生成的素数的二维列表
box = [[] for j in range(a2 * b2)] 
# 存储对应a、b乘积的二维列表
box_ab = [[] for j in range(a2 * b2)] 

for a in range(a_lower_limit, a_upper_limit):
    for b in range(b_lower_limit, b_upper_limit):
        a_prime = a + a1       
        for n in range(0, b_upper_limit):                       
            num = n**2 + a*n + b
            if isprime(num):          
                   box[(a_prime * b2) + b].append(num) 
                   box_ab[(a_prime * b2) + b].append(a*b)

# 找到box中最长的子列表
def max_length_list(box):
    max_length = max(len(x) for x in box)
    max_list = max(box, key=len)
    return (max_list)

# 获取最长子列表的索引并输出对应a*b
x = box.index(max_length_list(box))
print((box_ab[x])[0]) 

print(f"Run time: {(time.time() - start_time):.2f} seconds")

原代码逻辑与优化需求 #

原代码逻辑：对每一组a、b组合，计算从n=0开始连续生成的素数，存入二维列表box的对应子列表中，最后找出最长子列表对应的a*b。

我希望将二维box替换为一维列表box = []，配合初始为0的变量max_number_primes：针对每一组a、b组合，将生成的素数存入一维列表，处理完该组后比较列表长度与max_number_primes，若更长则更新最大值，最终找到对应a*b。

尝试的错误代码 #

a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0 # 暂时设为0
b_upper_limit = 1001
a1 = abs(a_lower_limit)
b1 = abs(b_lower_limit) # 若b下限为0则无需此变量
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit

box = [] # 存储素数的一维列表
max_number_primes = 0

for a in range(a_lower_limit, a_upper_limit):
    for b in range(b_lower_limit, b_upper_limit):
        if a_lower_limit < 0:
            a_prime = a + a1
        else:
            a_prime = a - a_lower_limit       
        for n in range(0, b_upper_limit):                       
            num = n**2 + a*n + b
            if isprime(num):          
                box.append(num)
                if len(box) > max_number_primes:
                    max_number_primes = len(box)
                    box.clear

正确实现方案 #

核心思路 #

不需要存储所有素数，只需统计每组a、b生成的连续素数个数，同时记录当前最大个数对应的a*b即可。如果一定要用一维列表，需为每组a、b单独维护临时列表，处理完就清空或重置。

修改后的代码（一维列表版本） #

import time
from sympy import isprime

start_time = time.time()

a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0
b_upper_limit = 1001

max_count = 0
best_product = 0

for a in range(a_lower_limit, a_upper_limit):
    for b in range(b_lower_limit, b_upper_limit):
        current_primes = []  # 每组a、b对应的临时一维列表
        n = 0
        while True:
            num = n**2 + a*n + b
            if isprime(num):
                current_primes.append(num)
                n += 1
            else:
                break
        # 更新最大连续素数个数及对应乘积
        if len(current_primes) > max_count:
            max_count = len(current_primes)
            best_product = a * b

print(best_product)
print(f"Run time: {(time.time() - start_time):.2f} seconds")

进一步提速建议 #

1. 筛选b的范围：当n=0时，公式结果为b，因此b必须是素数。提前生成0-1000的素数列表，只遍历这些b，能减少大量无效计算。
2. 替换素数检测函数：sympy的isprime效率较低，可自行实现米勒-拉宾素性测试，或提前生成埃氏素数筛，大幅提升素数判断速度。
3. 提前终止循环：当当前连续素数个数已小于等于max_count时，可直接终止该组a、b的n循环，无需继续计算。

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