Goldbach's Conjecture I am doing an exercise on finding the nearest pair of prime numbers p₁ and p₂ such that:


p₁ ≤ p₂
p₁ + p₂ = n (for 4 ≤ n ≤ 10⁷)
p₁ and p₂ are primes
p₂ - p₁ is minimal


I think it should work perfectly except that it got a TLE. Can someone point out how can I avoid it?

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 &gt;&gt; 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n &lt; 1373653:
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n &lt; 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 &gt; 4:
        for smaller in range(n // 2, -1, -1):
            if n - smaller &gt;= smaller:
                if is_prime(n - smaller) and is_prime(smaller):
                    print (smaller, n - smaller)
                    flag = True
                    break
    else:
        print ('2 2')


main()
My solution consists of a single change:


Changed the is_prime function into a prime sieve (from this answer) + lookup


My final code (Also handled odd numbers just for fun, definitely not because I misread the question):

def main():
    import itertools
    import math
    izip = itertools.zip_longest
    chain = itertools.chain.from_iterable
    compress = itertools.compress
    def rwh_primes2_python3(n):
        """ Input n&gt;=6, Returns a list of primes, 2 &lt;= p &lt; n """
        zero = bytearray([False])
        size = n//3 + (n % 6 == 2)
        sieve = bytearray([True]) * size
        sieve[0] = False
        for i in range(int(n**0.5)//3+1):
          if sieve[i]:
            k=3*i+1|1
            start = (k*k+4*k-2*k*(i&amp;1))//3
            sieve[(k*k)//3::2*k]=zero*((size - (k*k)//3 - 1) // (2 * k) + 1)
            sieve[  start ::2*k]=zero*((size -   start  - 1) // (2 * k) + 1)
        ans = [2,3]
        poss = chain(izip(*[range(i, n, 6) for i in (1,5)]))
        ans.extend(compress(poss, sieve))
        return ans

    string2 = "Impossible"
    n = int(input())
    sieve = [t for t in rwh_primes2_python3(n) if t &lt;= math.floor((n // 2) / 2) * 2 + 1][::-1]
    another = [t for t in rwh_primes2_python3(n) if t &gt;= math.floor((n // 2) / 2) * 2 + 1]

    if n &gt; 5 and n % 2 == 0:
        for smaller in sieve:
            if n - smaller in another:
                print (smaller, n - smaller)
                break
    elif n % 2 == 1 and n != 5:
        if n - 2 in another or n-2 in sieve: print (2, n-2)
        else: print ('Impossible')
    elif n == 4:
        print ('2 2')
    else:
        print ('2 3')

main()