python - 哥德巴赫猜想 - 找出偶数可以写成两个素数之和的方式的数量

Question

我想知道给定的正偶数可以写成两个素数之和的方式的数量。

目前，我有这段代码:

n = int(input(">"))
def genprimes(n):#generate primes from 2 to n
    primes = []
    for i in range(2,n):
        prime = True
        for a in range(2,i):
            if i % a == 0:
                prime = False
        if prime == True:
            primes.append(i)
    return primes

pairs = []
primes = genprimes(n)

for prime1 in primes:
    for prime2 in primes:
        if prime1 + prime2 == n and [prime1,prime2] not in pairs and [prime2,prime1] not in pairs:
            pairs.append([prime1,prime2])
print(len(pairs))

它可以工作，但是当 n 超过 10,000 时它会变得有点慢。谁能想出一种更有效的方法来找到这个值，以便快速产生高值的结果？

Answer 1

你有两个慢速算法。

要获得质数列表，您需要分别检查每个数的质数。获取素数列表的最快方法是使用预先构建的素数列表——这就是我为此类问题所做的。最多 2**16 (65,536) 个素数的列表只需要 6542 个整数，我将该列表存储在一个模块中。您可能更喜欢使用 Sieve of Eratosthenes这通常被认为是从头开始获取此类列表的最快方法。

然后您尝试每对质数，看它们是否加到您的目标数。对于每个素数 p，查看 n-p 是否也是素数会更快。正如@Shubham 所建议的那样，您可以使用二进制搜索来检查 n-p ，但是拥有两个索引可能会更快，一个定期上升并产生 p ，另一个继续根据需要检查 n-p。将您的素数列表复制到一个集合并使用它来检查 n-p 是否在列表中可能是最快的。这最后两种技术的顺序为 n，但对于最多 10,000 的数字，开销可能会影响哪种技术最好。是的，对于此类问题，10,000 并不是很大。最后，如果内存不是问题，@BoulderKeith 指出您可以将素数列表保留为 bool 值列表(真/假)并快速检查 n-p 是否为素数——这是所有技术中最快的，如果最耗费内存的话。