Python实现哥德巴赫猜想时重复素数对问题的解决方法

你的问题根源在于遍历所有素数时，没有限制素数对的顺序，导致正序和逆序的对（比如(3,23)和(23,3)）都被加入结果。核心解决思路是只保留满足num <= diff的素数对，或者直接将遍历范围限制在不超过n//2的素数，这样就能彻底避免重复。

修改后的代码（基础版） #

import math

def prime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def Plist(n):
    res = []
    for i in range(2, n + 1):
        if prime(i):
            res.append(i)
    return res

def Goldbach(n):
    res = []
    plist = Plist(n)
    for num in plist:
        diff = n - num
        # 通过num <= diff过滤逆序对
        if diff in plist and num <= diff:
            res.append((num, diff))
    return res

优化版（减少循环次数） #

如果想进一步提升效率，可以直接把遍历范围限制在不超过n//2的素数——因为当素数超过n//2时，对应的diff必然小于当前素数，对应的素数对已经在之前的遍历中被记录过了：

def Goldbach(n):
    res = []
    plist = Plist(n)
    for num in plist:
        # 素数超过n的一半时，直接终止循环
        if num > n // 2:
            break
        diff = n - num
        if diff in plist:
            res.append((num, diff))
    return res

关键说明 #

1. 给prime函数补充了n <=1的边界判断，避免传入非素数的小数值时出错
2. 去掉了原代码中的hmap，因为通过顺序限制已经能完全避免重复，不需要额外的哈希表存储
3. 优化版的循环终止条件能减少一半左右的遍历次数，对于大数值的n更高效

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