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

✏️ 문제

9020번: 골드바흐의 추측

✏️ 풀이

모든 짝수는 두 소수의 합으로 표현이 된다.

이 때 모든 짝수 n = n/2 + n/2로 표현이 가능하다.

따라서 이를 중심으로 왼쪽항은 1 빼주고 오른쪽 항은 1더해주면 모든 합의 경우의 수를 표현할 수 있다.

이 때 두 항이 소수인 것 중 가장 작은 것을 출력해준다.

이 풀이에서는 중앙에서 시작했으므로 소수인 첫번째 경우가 가장 차이가 적게 된다. 따라서 바로 break한다.

✏️ 코드

from math import sqrt

# 10000까지의 소수
sosu = []
for i in range(2, 10000):
    for j in range(2, int(sqrt(i)) + 1):
        if i % j == 0:
            break
    else:
        sosu.append(i)

T = int(input())
for _ in range(T):
    n = int(input()) # 두 소수의 합으로 나타내짐

    # 무조건 짝수 차이남
    diff = 0
    while True:
        a = int(n/2 - diff/2)
        b = int(n/2 + diff/2)
        if a in sosu and b in sosu:
            print(a, b)
            break
        else:
            diff += 2