[백준 9020번-파이썬/Python] 골드바흐의 추측

http://acmicpc.net/problem/9020

{코드}

data = [int(input()) for _ in range(int(input()))]
n = max(data)
sieve = list(range(n+1))
sieve[0], sieve[1] = 0, 0
for i in range(2, n+1):
  if sieve[i]:
    for t in range(i+i, n+1, i):
      if sieve[t]:
        sieve[t] = 0
for n in data:
	p, q = n//2, n//2
	while True:
		if sieve[p] and sieve[q]:
			print(p, q)
			break
		else:
			p -= 1
			q += 1

{설명}

최대한 n을 이루는 수의 차가 작아야하므로 n의 절반에서 시작해서 n을 만드는 소수 두개를 에라토스테네스의 체에서 찾으면 된다.

*처음에 실행시간이 7000ms대가 나와서 수정을 거치니 최종적으로 284ms가 나왔다.