백준 9020번 - 골드바흐의 추측

이번 문제도 베르트랑 공준 문제처럼 먼저 소수를 모두 구한 뒤에 반복문을 이용해서 구해주면 될 것이다.

문제의 핵심은 2부터 증가하면서 둘다 소수이면 출력해주면 되는 것인데, 출력할 때 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력하고, 출력하는 소수는 작은 것부터 먼저 출력해야한다.

그러려면 min 변수와 gap 변수를 이용해서 gap을 매번 구해준 뒤 min과 비교해서 gap이 더 작으면 gap을 min에 넣어준 뒤 반복해서 비교해주면 되겠다.

##변수 선언 부분
T = 0
n = 0
min = 100000
gap = 0
save = 0
##메인 함수 부분
if __name__ == "__main__":
    T = int(input())
    prime = 10001 * [True] 
    for i in range(2,101): #제곱근만큼 반복
        for j in range(2*i,10001,i): #본인의 배수를 모두 지워준다.
            if prime[j]:
                prime[j] = False
    for _ in range(T):
        n = int(input())
        min = 100000
        gap = 0

        for i in range(2,n): #2부터 반복
            if prime[i] and prime[n-i]: #i와 n에서 i를 뺀 값이 모두 소수면
                if i>n-i: #gap이 -값이 나올 수 있기 때문에 경우를 나눠준다.
                    gap = 2*i - n
                else:
                    gap = n - 2*i
                if(gap<min): #차이가 가장 작은 값을 출력해야하기 때문에
                    min = gap #최솟값을 찾아준다
                    save = i #값 저장
        print('%d %d'%(save,n-save))

처음에 이 문제를 풀 때 에라토스테네스의 체를 사용하지 않고 일반적인 소수 판별법을 사용했다가 시간 초과가 떴다.

소수 문제를 풀 때는 웬만하면 에라토스테네스의 체를 사용하는 것이 좋을 것 같다. 코드가 일반적인 판별법보다 그렇게 복잡한 것도 아니기 때문에 기본으로 사용하는 것도 좋은 방법인 것 같다. 골드바흐 파티션에 대해 배운 문제였다.