📢 9020번 문제

골드바흐의 추측

백준 문제 링크

🔎 풀이

사용언어 : python

• n의 범위가 4 ≤ n ≤ 10,000 이므로 먼저 10000까지의 소수를 에라토스테네스의 체를 이용하여 다 구한다.
• 입력받은 숫자(y)를 반으로 나눈 값(z)부터 + 1을 해가며 소수를 찾는다.
• 찾은 소수를 m이라 한다.
• y - m 또한 소수 일때 m과 y-m이 정답이다.

🔎 코드

# 먼저 에라토스테네스의 체로 소수를 다 구하기
result = [True] * 10001
result[1] = False
for i in range(2, 10001):
    if result[i]:
        a = 2
        while a * i <= 10000:
            result[i * a] = False
            a += 1

# 숫자를 반으로 나눈 값부터 소수를 찾는다.
# 숫자 - 찾은 소수 = 소수 일 경우 정답이다.

n = int(input())

for x in range(n):
    y = int(input())
    z = y//2
    for m in range(z, y):
        if result[m] and result[y-m]:
            print(y-m, m)
            break