[BOJ] 9020 | 골드바흐의 추측

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

골드바흐의 추측은 유명한 정수론의 미해결 문제로 알려져있다.
2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 추측인데 이러한 수를 골드바흐의 수라고 하고, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

이 문제는 2보다 큰 짝수 n이 주어졌을때, n의 골드바흐 파티션을 출력하는 코드를 작성하는것이다.

이 문제는 에라토스테네스의 체를 통해 소수 리스트를 먼저 구한다.
이 후에 소수이면서, 두 수의 차가 가장 적으며, 두 수를 더했을 때 입력값을 만족시키는 두 수를 구하면 된다.
두 수의 차가 가장 작은 경우를 구하는 게 이 문제의 핵심이다.
두 수를 a, b라고 했을 때, 두 수를 입력값인 n의 절반 값인 n/2로 두고 하나는 증가, 하나는 감소시키면서 소수임을 체크한다. 둘 다 소수일 때 출력한다.
아래 코드에서는 a는 감소, b는 증가하여 출력한다.

코드

---

def prime_list():       # 에라토스테네스의 체로 소수 리스트 구하기
    n = 10001           # 문제에서 제시한 조건
    sieve = [True] * n

    for i in range(2, int(n ** 0.5)+1):
        if sieve[i]:
            for j in range(i+i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]


T = int(input())

Prime = prime_list()

for i in range(T):
    n = int(input())

    a = n // 2
    b = n // 2

    while True:
        if a and b in Prime:
            print(a, b)
            break
        else:
            a -= 1
            b += 1

결과

---