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

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

---

문제 설명

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

📌 시간 제한: 2초

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

---

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

---

문제 접근

골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 가설이다. 이번 문제에서는 주어진 짝수 n에 대해 두 개의 소수의 합으로 표현하는 방법을 찾고, 그중에서 차이가 가장 적은 소수 쌍을 출력해야 한다.

이 문제를 해결하기 위해서는 먼저 n 이하의 소수들을 판별할 수 있어야 한다. 그리고 그 소수들 중에서 어떤 두 수의 합이 n이 되는지를 찾아야 한다. 이를 위해 가장 기본적인 접근 방식은 n // 2부터 시작해서 (i, n - i)가 모두 소수인지 확인하는 것이다.

 

소수 판별이 필요하므로, 이전에 베르트랑 공준 문제를 해결할 때 사용했던 소수 판별 함수(is_prime)를 그대로 활용할 수 있다. 두 문제 모두 소수를 판별하는 과정이 필요하지만, 문제의 목표와 소수를 활용하는 방식에는 차이가 있다.

베르트랑 공준에서는 n < x ≤ 2n 범위 내에서 소수가 몇 개 있는지를 구하는 것이 목표였다. 따라서 모든 x에 대해 한 번씩 is_prime(x)을 호출하면서 개수를 세면 되었다. 이 과정에서 각 숫자는 독립적으로 판별되며, 특정 숫자가 다른 숫자와 연관되지 않는다.

반면, 골드바흐의 추측에서는 n을 두 개의 소수의 합으로 나타내야 한다. 즉, 단순히 특정 범위 내 소수 개수를 구하는 것이 아니라, 두 개의 소수를 조합하여 n을 만들 수 있는지 확인해야 한다. 이를 위해 n // 2부터 시작하여 (i, n - i) 형태로 두 숫자가 모두 소수인지 확인하는 방식으로 접근한다. 결국 두 문제 모두 is_prime()을 사용하지만, 하나는 개수를 세는 방식이고, 하나는 조합을 찾는 방식이라는 차이가 있다.

이 문제를 해결하기 위해서는 is_prime()을 반복적으로 호출하면서 적절한 (i, n - i)를 찾으면 되므로, 단순한 소수 판별 방식을 그대로 적용할 수 있다.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):  # 2부터 √n까지 나누어보며 소수 판별
        if n % i == 0:
            return False
    return True

def find_goldbach_partition(n):
    for i in range(n // 2, 1, -1):  # n의 절반부터 탐색
        if is_prime(i) and is_prime(n - i):  # 두 수가 모두 소수인지 확인
            return i, n - i

t = int(input().strip())
numbers = [int(input().strip()) for _ in range(t)]

for n in numbers:
    p1, p2 = find_goldbach_partition(n)
    print(p1, p2)

 

위 코드의 문제점

이때 소수 판별을 위해 사용하는 함수 is_prime(n)은 O(√N)의 연산을 수행한다. 즉, 특정 숫자가 소수인지 판별하기 위해 최대 √N번의 나눗셈 연산을 진행해야 한다. 따라서 한 번 is_prime(n)을 호출하는 데 걸리는 시간 복잡도는 O(√N)이다.

그런데 find_goldbach_partition(n) 함수에서는 i = n // 2부터 1까지 순차적으로 내려가면서 (i, n - i)가 모두 소수인지 검사해야 한다. 최악의 경우 i = 2까지 모든 i를 검사해야 하므로, O(N)번 반복문이 실행될 수 있다. 그리고 각 i마다 is_prime(i)와 is_prime(n - i)를 호출하므로, 반복문 한 번당 O(√N)의 연산이 이루어진다.

결과적으로 O(N)번 반복하는 과정에서 매번 O(√N)의 연산을 수행하므로, 전체적인 시간 복잡도는 O(N√N)이 된다.

이 방식은 n이 커질수록 실행 시간이 급격히 증가할 수 있다. 다만, 일반적인 입력 크기에서는 실행이 가능하지만, n이 커질 경우 연산량이 많아져 실행 속도가 느려질 수 있다. 따라서 더욱 효율적인 방법을 적용하여 최적화하는 것이 바람직하다. 이전 문제였던 베르트랑 공준에서도 소수 개수를 구하는 과정에서 소수 판별을 반복적으로 수행하는 것이 비효율적이었고, 이를 해결하기 위해 에라토스테네스의 체를 사용하여 미리 소수를 구해두는 방식으로 최적화했었다.

 

에라토스테네스의 체

이 방식으로 구현하면 소수를 판별할 때마다 is_prime(n)을 호출하는 대신, 미리 구해둔 소수 리스트를 조회하는 방식으로 변경되므로 판별 속도가 획기적으로 빨라진다.

이전 방식에서는 find_goldbach_partition(n) 함수가 실행될 때마다 is_prime(n)을 호출했기 때문에 각 n마다 O(N√N)의 연산이 필요했다. 하지만, 에라토스테네스의 체를 사용하면 소수 여부를 미리 저장해두고 단순한 배열 조회만 하면 되므로 각 소수 판별 연산이 O(1)로 줄어든다.

즉, 전체적인 시간 복잡도는 소수를 미리 구하는 O(N log log N) + 골드바흐 파티션을 찾는 O(N) = O(N log log N) + O(N)이 된다. 이는 이전 방식의 O(N√N)보다 훨씬 빠르며, n이 커질수록 차이가 더욱 커진다.

---

구현

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0], is_prime[1] = False, False
    
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    
    return is_prime

def find_goldbach_partition(n, is_prime):
    for i in range(n // 2, 1, -1):
        if is_prime[i] and is_prime[n - i]:
            return i, n - i

t = int(input().strip())
numbers = [int(input().strip()) for _ in range(t)]

limit = max(numbers)
is_prime = sieve_of_eratosthenes(limit)

for n in numbers:
    p1, p2 = find_goldbach_partition(n, is_prime)
    print(p1, p2)