[백준/Python] 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

n = int(input())
prime = [0, 0] + [1] * 9999 # 소수 리스트

# 에라토스테네스의 체를 이용하여 소수 구하기
for i in range(2, int(10000 ** 0.5)+1):
	if prime[i]:
		for j in range(i*2, 10001, i):
			prime[j] = 0

# 두 소수의 차이가 가장 작은 골드바흐 파티션 구하기
for _ in range(n):
	num = int(input())
	idx = 0
	while True:
		if prime[num // 2 - idx] and prime[num // 2 + idx]:
			print(num // 2 - idx, num // 2 + idx)
			break
		idx += 1

1. 에라토스테네스의 체를 이용하여 소수를 구한다.

    1-1. 매번 소수를 구하는 것보다 입력받는 숫자가 10000까지로 특정 되어 있으므로 미리 소수를 구하는 것이 효율적이다.

2.  골드바흐 파티션을 구한다.

    2-1. 두 소수의 차이가 가장 작아야 하므로 입력받은 숫자의 가운데부터 탐색한다.

    2-2. 두 소수의 합이 num인 것을 찾지 못하면 idx에 +1 을 한다.

    2-3. 두 소수의 합이 num인 것을 찾으면 결과를 출력하고 반복문을 빠져나온다.