Skip to main content
 首页 » 编程设计

python之检查哥德巴赫猜想是否成立 N

2025年02月15日13Leo_wl

我被要求编写一段代码来检查哥德巴赫猜想是否对每个不超过 N 的偶数都成立,到目前为止我有以下内容:

def gb(n): 
    #give a list of all primes less than n using the sieve of Eratosthenes (not considering 1 to be prime like Goldbach): 
    primes=list(range(2,n+1)) 
 
    for i in primes: 
 
        j=2 
 
        while i*j<=primes[-1]: 
            if i*j in primes : 
                primes.remove(i*j) 
                j=j+1 
 
    #give a list of even numbers less than n but starting from 4 
    evens=list(range(4,n+1,2)) 

然后我需要检查偶数中的所有数字是否都可以作为素数中的两个数字之和。我现在很困惑,我知道我需要使用循环,但我不确定如何检查它们是否都符合猜想?

请您参考如下方法:

与其遍历所有偶数,并为每个检查是否存在两个素数的组合与该数字之和相反,您可以执行相反的操作:收集一个集合中两个素数的所有总和(快速查找O(1)) 并针对每个偶数检查它是否在该集合中。

>>> N = 1000 
>>> primes = [p for p in range(N+1) if not any(p % q == 0 for q in range(2, p//2))] 
>>> evens = [n for n in range(4, N+1, 2)] 
>>> sums = set(p + q for p in primes for q in primes) 
>>> all(n in sums for n in evens) 
True 

当然,使用筛子可以更有效地实现素数,但这在这里并不重要。给定素数,检查数字的复杂度为 O(P^2 + N),其中 P 是小于 N 的素数数。

或者,如果您不想计算和存储两个素数的所有 P^2 组合的总和,您可以将素数变成一个集合,并且对于每个偶数 n,找到一个素数 p 使得 n - p 也在 primes 中。这将具有 O(N * P) 的复杂度,但需要更少的空间

>>> primes = set(primes) 
>>> all(any(n - p in primes for p in primes) for n in evens)