Проверка гипотезы Гольдбаха верна до 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)