[백준] 9020 골드바흐의 추측

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

import sys
input = sys.stdin.readline

#에라토스테네스의 체로 소수를 먼저 구함
max_number= 10000
prime=[False,False,]+[True]*(max_number - 1)
for i in range(2,int(max_number**0.5)+1):
    if prime:
        for j in range(2*i,max_number+1,i):
            prime[j] = False
prime_num = [i for i,v in enumerate(prime) if v] #1229개

t = int(input())
for tc in range(1, t + 1):
    n = int(input())
    # n을 2로 나눈 수에서 가장 큰 소수부터 2까지 확인, (n-i) 가 소수인지확인
    for i in range(n//2,1,-1): # n=4, i=2
        if prime[i] and prime[n-i]:
            s,b = i, n-i
            break
    print(f"{s} {b}")

---

에라토스테네스의 체로 소수를 먼저 구하고, 이후에 짝수들의 골드바흐 파티션을 찾았다. 골드바흐 파티션이란 해당 수가 두 소수의 합으로 이루어질때 두 소수를 뜻한다.

골드바흐 파티션에서 두 소수의 차이가 가장 작은 것을 출력해야하기 때문에 중간부터 비교를 해야한다는 생각을 했다.

그래서 범위를 중간부터 2까지 잡아서 반복문을 돌렸다. range(n//2,1,-1)

반복문 안에서 숫자가 소수(prime[i] == True) 이면, 반대수(n-i)가 소수인지 확인하였고, 가장 먼저 찾는 골드바흐 파티션이 차이가 가장 작기때문에 break으로 멈추었더니 해결되었다.