[파이썬(Python)] 백준 6588번 골드바흐의 추측

 

 

백준 6588번: 골드바흐의 추측

문제 바로 가기

---

📌 문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다.
또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

입력
입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.

 

출력
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다.이때, a와 b는 홀수 소수이다.
숫자와 연산자는 공백 하나로 구분되어져 있다.
만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다.
또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

 

 

📝 문제 접근 방법

문제 분석

• 문제 요약
  • 주어진 짝수 $n$을 두 홀수 소수의 합으로 표현하는 프로그램을 작성합니다.
  • 소수 $a$, $b$는 홀수이고, $a + b = n$을 만족해야 합니다.
  • 가능한 경우 중에서 $b - a$가 가장 큰 값을 출력합니다.
  • $n$이 두 홀수 소수의 합으로 표현되지 않는 경우 "Goldbach's conjecture is wrong."을 출력합니다.

 

• 제약 조건
  • 입력 범위: $6 \leq n \leq 1,000,000$
  • 입력이 여러 개 주어지며, 마지막 입력은 0입니다.
  • 효율적인 소수 판별이 필요합니다.

 

아이디어

• 소수 판별: 에라토스테네스의 체
  • $1,000,000$ 이하의 모든 소수를 효율적으로 판별하기 위해 에라토스테네스의 체를 사용합니다.
  • 작동 방식
    1. 2부터 시작하여 소수의 배수들을 모두 제거합니다.
    2. 제거는 소수의 제곱수부터 시작합니다. ($i \times i$ 이전의 배수들은 이미 제거된 상태입니다.)
    3. 이 과정을 $\sqrt{n}$ 까지만 반복하면 모든 소수를 판별할 수 있습니다.
  • 결과
    • 소수 여부를 저장한 배열 is_prime을 생성하여 $O(1)$로 특정 숫자가 소수인지 확인할 수 있습니다.
    • 소수만 모은 리스트 prime_numbers를 생성하여 탐색 범위를 제한합니다.

 

• 두 소수의 조합 탐색
  • 입력으로 주어진 짝수 $n$ 에 대해 두 소수의 합으로 표현할 수 있는 조합을 찾습니다.
  • 탐색 전략
    • a를 3부터 시작하여 $n // 2$까지 증가시키며 a가 소수인지 확인합니다.
    • $b = n - a$를 계산한 후 $b$가 소수인지 확인합니다.
    • $a$와 $b$가 모두 소수라면 $n = a + b$를 출력하고 탐색을 종료합니다.
  • 탐색 범위 최적화
    • 두 숫자의 합이 대칭적이므로 $a$를 $n / / 2$까지만 탐색하면 충분합니다.
    • $b - a$가 최대가 되는 조합을 출력하려면 $a$를 작은 값부터 탐색합니다.

 

 

 

👩‍💻 나의 답안

import sys
import math

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

MAX_NUM = 1000000
prime_list = sieve_of_eratosthenes(MAX_NUM)

prime_numbers = [i for i in range(3, MAX_NUM + 1, 2) if prime_list[i]]

input_data = sys.stdin.read().strip().split()
results = []

for line in input_data:
    n = int(line)
    if n == 0:
        break
    
    found = False
    for a in prime_numbers:
        if a > n // 2:
            break
        b = n - a
        if prime_list[b]:
            results.append(f"{n} = {a} + {b}")
            found = True
            break
    
    if not found:
        results.append("Goldbach's conjecture is wrong.")

sys.stdout.write("\n".join(results) + "\n")

 

 

1. 에라토스테네스의 체로 소수 리스트 생성

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

• 목적: 최대 범위 max_num까지의 소수를 효율적으로 판별하기 위해 에라토스테네스의 체를 사용합니다.
• 작동 원리
  1. [0, max_num] 범위의 모든 숫자를 소수(True)로 초기화합니다.
  2. 0과 1은 소수가 아니므로 False로 설정합니다.
  3. 2부터 시작하여 현재 숫자가 소수라면 해당 숫자의 배수를 모두 False로 설정합니다.
  4. 이 과정을 $\sqrt{\text{max_num}}$까지만 반복하여 소수를 판별합니다.
• 결과: 소수 여부를 저장한 is_prime 리스트를 반환합니다.

 

2. 소수 리스트 생성

MAX_NUM = 1000000
prime_list = sieve_of_eratosthenes(MAX_NUM)
prime_numbers = [i for i in range(3, MAX_NUM + 1, 2) if prime_list[i]]

• prime_list: 최대 범위 1,000,000까지의 소수 여부를 저장한 리스트입니다.
• prime_numbers: 소수 중 홀수만 추출한 리스트입니다.
  • 짝수 소수는 2 하나뿐이므로 주어진 문제에서는 짝수의 두 소수 합만 구하므로 제외합니다.

 

3. 입력처리

input_data = sys.stdin.read().strip().split()
results = []

• input_data: 모든 입력을 한 번에 읽어 저장합니다.
• results: 각 테스트 케이스의 결과를 저장할 리스트입니다.

 

4. 골드바흐의 추측 검증

for line in input_data:
    n = int(line)
    if n == 0:
        break
    
    found = False
    for a in prime_numbers:
        if a > n // 2:  
            break
        b = n - a
        if prime_list[b]:
            results.append(f"{n} = {a} + {b}")
            found = True
            break
    
    if not found:
        results.append("Goldbach's conjecture is wrong.")

• 입력 값 처리
  • 각 입력 n에 대해 골드바흐의 추측을 확인합니다.
  • n이 0이면 반복을 종료합니다.
• 두 소수의 합 찾기
  • 홀수 소수 a를 순회하며 $b = n - a$를 계산합니다.
  • a와 b가 모두 소수(prime_list[a] 와 prime_list[b]가 True)인지 확인합니다.
  • 조건을 만족하면 결과를 저장하고 탐색을 종료합니다.
• 대칭성 활용
  • a를 $n // 2$까지만 탐색하면 됩니다.

 

 

 

✨ 새로 알게 된 점

1. 에라토스테네스의 체를 활용한 소수 판별과 효율적 출력 방식

에라토스테네스의 체를 이용해 소수 여부를 미리 계산해 리스트에 저장하는 방식이 매우 효율적이라는 점을 알게 되었습니다. 소수 여부를 저장한 prime_list를 통해 특정 숫자가 소수인지 바로 확인할 수 있었고, 소수만 담긴 prime_numbers를 활용하여 탐색 범위를 줄이는 데도 큰 도움이 되었습니다. 특히, 이렇게 데이터를 사전에 준비하면 중복 연산을 없앨 수 있어 대규모 입력에서도 빠르게 처리할 수 있다는 점이 인상적이었습니다.

또한, 여러 테스트 케이스를 처리할 때 결과를 한 번에 출력하는 방식이 입출력 시간을 줄이는 데 효과적이라는 점도 배울 수 있었습니다. Python의 join 메서드를 활용해 결과를 깔끔하고 효율적으로 출력할 수 있다는 점도 유익하게 느껴졌습니다.