[백준] 6588번 골드바흐의 추측 - Python

이번에 해결해 볼 문제는 백준에 있는 6588번 골드바흐의 추측입니다.

---

문제 설명

1. 입력으로 6보다 크거나 같고 1,000,000보다 작거나 같은 짝수가 주어집니다.
2. 4보다 큰 모든 짝수를 두 홀수 소수의 합으로 나타낼 수 있음을 골드바흐의 추측이라고 합니다.
3. 주어진 짝수에 대해서 골드바흐의 추측을 검증하는 것이 문제입니다.
4. 4보다 큰 짝수 n을 두 홀수 소수의 합으로 나타낼 수 있는 방법이 여러가지라면 그 차이가 가장 큰 것을 n = a + b형태로 출력하고 불가능한 경우에는 “GoldBach’s conjecture is wrong.”을 출력하면 됩니다.

문제 해결 아이디어

• $0 \le a, b \le 1,000,000$인 소수를 먼저 구해야 합니다.
• 합의 형태는 뺄셈의 형태로 변경가능하므로 가장 작은(큰) 소수부터 차례대로 n과의 차이를 구해봅니다.
  • 즉, $n - a = b$인데 $b$가 위에서 구한 소수에 포함되어 있는지 확인하면 됩니다.
  • 단, n의 절반($n//2+1$)이 넘어가는 경우 이전에 했던 연산들을 반복하는 것과 동일하므로 시간 단축을 위해 $n//2+1$까지만 탐색을 진행합니다.
• 만약 탐색을 모두 진행했을 때 골드바흐의 추측 검증이 실패하면 “GoldBach’s conjecture is wrong.”을 출력하면 됩니다.

문제 해결 코드

import sys

input = sys.stdin.readline

sosu = [True] * 2 + [False] * 999999
for i in range(2, int(1000000 ** 0.5) + 1):
    if not sosu[i]:
        for j in range(i * 2, 1000001, i):
            sosu[j] = True

while True:
    n = int(input())
    if n == 0:
        break
    for i in range(n - 1, n // 2 - 1, -2):
        if not sosu[i] and not sosu[n - i]:
            print(f"{n} = {n-i} + {i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

느낀 점

🤔 해당 문제의 시간 제한은 0.5초로 굉장히 짧습니다. 그렇기 때문에 시간을 줄일 수 있는 부분에서 최대한 줄여야 합니다. 저도 처음에는 실패를 하였고 해당 코드가 맞는 코드인지만을 확인하기 위해 pypy로 채점을 한 결과 성공했습니다. 이후 시간을 줄이지 못한 곳은 어디일지 계속 고민하였고 고민 끝에 두 곳을 줄일 수 있었습니다.

첫째, 소수를 구하는 부분에서 불필요한 부분을 삭제했습니다. 제가 위해서 소수를 구한 방식은 소수의 배수들은 모두 소수가 아니도록 표시하는 방법입니다. 그렇기 때문에 소수의 배수가 문제에서 주어진 최대값인 1,000,000이 넘어가는 순간부터는 소수를 구하지 않아도 됩니다. 그렇기 떄문에 다음과 같이 변경할 수 있었습니다.

# 변경 전
sosu = [True] * 2 + [False] * 999999
for i in range(2, 1000001):
    if not sosu[i]:
        for j in range(i * 2, 1000001, i):
            sosu[j] = True

# 변경 후
sosu = [True] * 2 + [False] * 999999
for i in range(2, int(1000000 ** 0.5) + 1):
    if not sosu[i]:
        for j in range(i * 2, 1000001, i):
            sosu[j] = True

둘째, $n=a+b$를 구하는 부분에서 시간을 조금이나마 더 줄일 수 있었습니다. 짝수인 경우 2를 제외하면 모두 소수가 되지 못하기 때문에 반복문을 돌면서 굳이 한 번씩 확인할 필요가 없었습니다. 아래 코드에서와 같이 반복문을 돌때 하나가 아닌 두 스텝씩 소수인지 확인하며 시간을 더 단축시킬 수 있었습니다.

# 변경 전
while True:
    n = int(input())
    if n == 0:
        break
    for i in range(n - 1, n // 2 - 1, -1):
        if not sosu[i] and not sosu[n - i]:
            print(f"{n} = {n-i} + {i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")

# 변경 후
while True:
    n = int(input())
    if n == 0:
        break
    for i in range(n - 1, n // 2 - 1, -2):
        if not sosu[i] and not sosu[n - i]:
            print(f"{n} = {n-i} + {i}")
            break
    else:
        print("Goldbach's conjecture is wrong.")