戈德巴赫猜想

Question

我正在做一项关于寻找最近的素数p₁和p₂的练习，这样：

• P₁≤p₂
• p₁+ p₂=n(对于4≤n≤10⁷)
• p₁和p₂是素数
• p₂- p₁是极小的

我认为它应该工作得很好，只是它有一个TLE。有人能指出我怎样才能避免吗？

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()

Answer 1

我的解决方案由一个变化组成：

• 将is_prime函数转换为素筛(从这个答案) +查找

我的最后代码(也只是为了好玩而处理奇数，绝对不是因为我误解了这个问题)：

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>=6, Returns a list of primes, 2 <= p < 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&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 <= math.floor((n // 2) / 2) * 2 + 1][::-1]
    another = [t for t in rwh_primes2_python3(n) if t >= math.floor((n // 2) / 2) * 2 + 1]

    if n > 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()