Гипотеза Гольдбаха


Я делаю упражнения на нахождение ближайшей пары простых чисел p₁ и p₂ такие, что:

  • p₁ ≤ p₂
  • p₁ + p₂ = N (для 4 ≤ н ≤ 10⁷)
  • p₁ и p₂ являются простыми
  • p₂ - p₁ минимальна

Я думаю, он должен работать идеально за исключением того, что он получил права. Может кто-то указывать, как я могу избежать этого?

import math
import random

def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2 ** i * d, n) == n - 1:
            return False
    return True  # n  is definitely composite


def is_prime(n, _precision_for_huge_n=16):
    if n in _known_primes:
        return True
    if n in (0, 1) or any((n % p) == 0 for p in _known_primes):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653:
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001:
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))


_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]

def main():
    n = int(input())
    if n > 4:
        for smaller in range(n // 2, -1, -1):
            if n - smaller >= smaller:
                if is_prime(n - smaller) and is_prime(smaller):
                    print (smaller, n - smaller)
                    flag = True
                    break
    else:
        print ('2 2')


main()


Комментарии