[Seop's의 코드풀이] 백준 9020 골드바흐의 추측 - Python

 이번에 풀어볼 문제는 백준 9020번인 골드바흐의 추측이라는 문제입니다.

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

문제를 보면 일단 소수를 구할 수 있어야 한다.

여러가지 테스트케이스가 주어짐으로 필자는 10000까지의 소수를 전부 구한 후에 문제를 풀었다.(사실 이과정만 잘 한다면 문제는 쉽다.)

소수를 구하는 방법으로는 에라토스테네스의 체 라는 방법을 사용했다.

에라토스테네스의 체는 2부터 시작하여 각 해당하는 배수를 지워나가는 것이다.(2를 제외한 2의 배수를 모두 제거)

즉 체 처럼 하나씩 거르는 것인데 어떻게 보면 무식할 수 있으나 컴퓨터의 입장에서는 나름 괜찮은 방법이다. 자세한 내용은 다음과 같다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

소수들을 구했다면 내가 찾고자 하는 짝수어 어떤 소수로 이루어져있는지만 찾으면 된다.

2개 이상의 경우도 찾아야 함으로 필자는 모두 찾아 주었다. 방법은 다음과 같다.

 

- 내가 찾고자 하는 수(N) - 1 부터 시작해서 N/2 까지 소수인지 확인한다.

- 해당하는 수가 소수이고 N - 해당하하는 수 도 소수이면 정답후보에 추가한다.

- 정답후보들 중 두수의 차가 가장 작은 값이 정답이다.

 

전체적인 코드는 다음과 같습니다. 질문과 피드백은 언제나 감사합니다.

 

import sys
input = sys.stdin.readline

def getPrimeNumber() :
    answer = dict()
    prime = [True for i in range(10001)]
    for i in range(2, 10001) :
        if prime[i] :
            answer[i] = True
            for j in range(i*2, 10001, i) :
                prime[j] = False
    return answer

num = getPrimeNumber()

def soluction() :
    n = int(input())
    result = []
    for i in range(n-1, n//2 - 1, -1) :
        if i in num and (n-i) in num :
            result.append([i, n-i])

    result = sorted(result, key= lambda x: (abs(x[0]- x[1])))
    ans = sorted(result[0])
    return str(ans[0]) + " " + str(ans[1])

if __name__ == "__main__":
    c = int(input())
    for _ in range(c) :
        print(soluction())