检验哥德巴赫猜想是否成立 N

Question

我被要求编写一段代码来检查哥德巴赫猜想对于 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))

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

Answer 1

无需循环遍历所有偶数，并且每次检查是否存在两个素数的组合，其总和等于该数字，您可以执行相反的操作：收集集合中两个素数的所有和（在 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

当然，使用筛子可以更有效地实现

primes

，但这与这里无关。给定

primes

，检查数字的复杂度为 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)

Answer 2

这应该可以做到：

import itertools
import math

def check(n, primes):
    """Check if Goldbach's conjecture holds for n, given a list of primes"""

    for a,b in itertools.product((p for p in primes if p<n), repeat=2):
        if a+b == n: return True
    return False


def checkAll(N):
    """Check whether Goldbach's conjecture holds for all even numbers >2, <=N"""

    primes = getPrimes(N)
    for n in range(4, N+1):
        if not check(n, primes): return False
    return True


def checkPrime(n, primes):
    """Check whether n is prime, given a list of prime numbers smaller than it"""
    for p in primes:
        if p > math.ceil(n**0.5): return True
        if not n%p: return False
    return True


def getPrimes(N):
    """Get all prime numbers <=N"""
    answer = [2,3]
    for n in range(5, N+1):
        if check(n): answer.append(n)

Answer 3

这里。 这保留了您最初想法的要点。 我刚刚在网上找到的筛子代码。

def sieve(x): 
   isprime = [False,True]*(x//2+1)
   isprime[1] = False
   isprime[2] = True
   for i in range(3, x+1, 2):
      if isprime[i]:
         for j in range(i*i, x, 2*i):
            isprime[j] = False
   return [i for i,v in enumerate(isprime) if v] 
    
def gb(n):
   ans = []
   #give a list of all primes less than n using the sieve of Eratosthenes (not considering 1 to be prime like Goldbach):
   primes = sieve(n)
   for i in primes:
      if i > n//2: break # avoids (3,7) and (7,3)
      if n-i in primes:
         ans += [(i,n-i)] 
   return ans
   
n = 200
#give a list of even numbers less than n but starting from 4
evens=list(range(4,n+1,2))
for i in evens:
    print(f"{i} {gb(i)}")