22359: Goldbach Conjecture

http://cs101.openjudge.cn/practice/22359/

Given the sum of prime A and prime B, find A and B.

输入

One positive integer indicating the sum (<= 10000).

输出

Two integers A and B.

样例输入

10

样例输出

3 7

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def goldbach(n):
    for i in range(2, n):
        if is_prime(i) and is_prime(n - i):
            return i, n - i

n = int(input())
a, b = goldbach(n)
print(a, b)

# 23n2300011075(才疏学浅)
from math import sqrt
n=10000
ls,x,y=[True]*(n+1),2,int(sqrt(n))+1
while x<y:
    if ls[x]==True:
        for i in range(x*2,n+1,x):
            ls[i]=False
    x+=1
ls=set([i for i in range(2,n+1) if ls[i]==True])

n=int(input())
for i in ls:
    if (n-i) in ls:
        print(i,n-i)
        break