Project Euler第58题代码错误排查：质数占比计算结果偏差

我正在解决Project Euler第58题，题目要求找出螺旋数对角线中质数占比降至指定百分比以下的临界点。

我先生成一定范围内的质数，再将对角线数字列表与质数列表对比计算占比，但结果远低于正确值：比如当占比低于10%时，我的结果是631，而正确答案约为26000。

我知道当前方法效率低会重新优化，但想先排查结果错误的原因。

我的代码 #

len_limit = 6 # 用于生成质数，我会根据计算进度调整这个限制
limit = 10 ** len_limit 
primes2 = [True] * (limit + 1)
primes2[0] = primes2[1] =  False
for i in range (2,int(limit ** 0.5) + 1):
    for n in range(2, int(limit / i) + 1):
        primes2 [i*n] = False
primes = []
for i in range(len(primes2)):
    if primes2[i] == True:
        primes.append(i)

def make_square(side_length): # 生成所有对角线数字的列表
    a,b = 0,0
    nums = [1]
    square_size = side_length
    for n in range(2,square_size): 
        nums.append(4 * n ** 2 - 10 * n + 7)    # NE
        nums.append((2*n - 1) ** 2)             # SE
        nums.append(4 * n ** 2 - 8 * n + 5)     # NW
        nums.append(4 * n ** 2 - 6 * n + 3)     # SW
    nums.sort()
    return nums

def fraction_prime(side_length):
    nums = make_square(side_length)
    a,b = 0,0
    for num in nums:
        if num in primes:
            a += 1
            b += 1
        else:
            b += 1
    return (a/b)

i = 3
while True:
    i += 1
    fraction_prime(i)
    side_length = 2 * i - 3
    # print(fraction_prime(i),side_length,i) # 可选，用于调试
    if fraction_prime(i) <= 0.40: # 不是题目要求的阈值，只是测试逻辑
        print(fraction_prime(i),side_length,i)
    if fraction_prime(i) < 0.40:
        break

错误原因分析 #

• 对角线数字生成逻辑错误
  make_square函数的循环范围和参数含义混淆：

  1. 循环range(2,square_size)会生成过多的对角线数字，比如当传入side_length=5时，循环n从2到4，生成3组共12个数字，加上中心1总共有13个，但边长为5的螺旋正方形对角线实际只有9个数字（中心1 + 两层，每层4个），这直接导致统计的总数b偏大，质数占比被错误拉低。
  2. 额外的nums.sort()完全没必要，且不会影响结果，但暴露了对生成逻辑的不清晰。

• 质数查询的范围限制与低效

  1. 预先生成的质数范围是10^len_limit，当对角线数字超过这个范围时，会被误判为非质数，导致质数计数a偏小，占比计算严重失真。比如正确答案对应的边长26000，最大对角线数是26000²=6.76×10^8，远大于10^6（当len_limit=6时），这些大数都会被错误判定为非质数，直接导致你得到的占比远低于真实值。
  2. 用num in primes判断质数是O(n)复杂度的线性查询，效率极低，但这不是结果错误的核心原因，只是性能问题。

• 主循环逻辑混乱
  主循环中i的递增逻辑和side_length的计算不匹配：side_length = 2*i -3，但你传入fraction_prime的参数是i而非side_length，导致make_square处理的参数含义错误，生成的数字对应层数和实际边长不匹配，进一步加剧统计错误。

修复方向 #

1. 修正对角线生成逻辑：
   明确螺旋正方形的边长与层数的关系：边长为2k+1（k从0开始，k=0对应边长1，k=1对应边长3），每层新增的4个对角线数公式为：

   • 右下角：(2k+1)²
   • 左下角：(2k+1)² - 2k
   • 左上角：(2k+1)² - 4k
   • 右上角：(2k+1)² - 6k
     循环k从1开始，每次只生成当前层的4个数，实时累加质数计数和总数，无需生成完整列表。

2. 替换质数判断方法：
   使用米勒-拉宾素性测试代替预先生成质数列表，该算法可以高效判断大数是否为质数，避免范围限制导致的漏判。

3. 简化主循环：
   直接按边长递增（每次+2，从3开始），每次计算当前边长下的对角线质数数量和总数，实时计算占比，直到满足题目要求的阈值。

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