BAEKJOON-9020 : 골드바흐의 추측

BEAKJOON-9020 : 골드바흐의 추측

이 문제 또한 에라토스테네스의 체를 이용했다.

미리 10000까지 소수를 구해놓고 시작했다.

이렇게 한 이유는 우선 문제 조건에서 두 소수의 합으로 짝수를 만들어야 하므로,

x가 입력 되었을 때, 합이 x가 되는 두 소수 a와 b 중, x의 가까운 소수일 수 있기 때문이다.

코드

n = int(input())
arr = [True] * 10001
for i in range(2, 101):
    if arr[i]:
        for j in range(i+i, 10001, i):
            arr[j] = False
for i in range(n):
    x = int(input())
    for j in range(x//2, 1, -1):
        if arr[j] and arr[x-j]:
            print(j, x-j)
            break

합이 x가 되는 두 소수를 구할 때 x의 반 부터 시작해서 1씩 감소하면서 for문을 돌린 이유는

파티션이 여러가지인 경우, 두 소수의 차가 가장 작은 값을 골라야 하기때문에 두 소수의 차가 작으려면 x의 중간 쯤에 있는 걸 먼저 골라서 출력하면 되겠다고 생각했다.

또한 작은 수가 앞에 나오기 때문에 x의 반부터 시작하여 2까지 찾아내도록 했다.