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

문제

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

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

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

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

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

실패(시간초과) 코드

import sys

def isPrime(n):
    if n < 2:
        return False
    elif n == 2 or n == 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(4, n):
        if n % i == 0:
            return False
    return True

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    for i in range(n, 1, -1):
        if isPrime(i):
            if n - i == 1:
                continue
            print(f"{n} = {n-i} + {i}")
            break

처음 무작정 풀었을 때는 시간 초과가 발생했다. n부터 1까지 -1씩 계속 돌면서 모든 수를 체크하고 있었다. 예를 들어 1 ~ 1000까지 검사하고 1001이 들어오면 또 1 ~ 1001까지 검사하고 이런 식으로 실행되다보니 시간초과가 발생하는 건 당연했다.

1부터 1,000,000까지 한 번만 모든 숫자를 탐색해서 홀수인지 아닌지 판별하고 이후 로직을 추가해야 한다.

문제에 나와있는 출력 부분 제대로 안 읽어서 'Goldbach's conjecture is wrong.' 출력하라는 부분도 빼먹음;

구글링 후 다시 짠 코드

import sys

# 에라토스테네스의 체
isPrime = [True] * 1000001
for i in range(2, 1001): # √10000000인 1000까지만 모든 수를 반복해서 소수를 찾으면 된다.
    if isPrime:
        for j in range(i + i, 1000001, i): # 2와 3은 어차피 소수, 4는 2로 만들어짐, 5도 소수 <- 이런 방식이기 때문에 i + i로 체를 더 빨리 만든다.
            isPrime[j] = False


while True:
    n = int(sys.stdin.readline())
    flag = True # 입력받은 수를 소수의 합으로 나타 낼 수 없는 경우, 주어진 문장을 출력하기 위한 변수
    if n == 0:
        break
    for k in range(3, n, 2):
        if isPrime[k] and isPrime[n-k]: # 'n = 소수(k) + 소수(n-k)'이어야 함으로 두 수가 모두 소수인지 판별
            if n-k == 1 or (n-k)%2 == 0: # n이 4일 경우 k가 3일 때 n-k는 1이 된다. 1은 소수가 아니기 때문에 n-k가 1일 경우를 잡아준다.
                continue
            print(f"{n} = {k} + {n-k}")
            flag = False
            break
    if flag:
        print("Goldbach's conjecture is wrong.")

에라토스테네스의 체를 사용했다. 전에 선형대수인가 자료구조인가 강의에서 슥 지나갔던 기억이 난다.

 

에라토스테네스의 체란 ?
1. 1부터 n까지의 숫자를 나열한다.
2. 소수가 아닌 1을 제거한다.
3. 2를 제외한 2의 배수를 제거한다. (2는 소수이므로)
4. 3을 제외한 3의 배수를 제거한다.
5. 4의 배수는 이미 2의 배수에서 지워졌으므로 반복할 필요가 없다.
6. 5를 제외한 5의 배수를 제거한다.
7. 7을 제외한 7의 배수를 제거한다.
8. 이와 같은 과정을 √n까지 반복한다.

 

 

이러한 해결 방법을 알고 나서도 범위가 1,000,000인데 100,000으로 잘못 입력하고, "Goldbach's conjecture is wrong." 출력 조건을 놓치는 등 자잘한 오류들로 시간을 꽤 잡아먹었다.