[BOJ][⚪1][백준#06588] 골드바흐의 추측

문제 출처

BAEKJOON Online Judge #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.”을 출력한다.

예제

입력

8
20
42
0

출력

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

My Sol

import sys
input = sys.stdin.readline

def check(N):
    def is_prime(n):
        for i in range(2, int(n ** (1 / 2)) + 1):
            if not n % i: return 0
        return 1

    def next_s(s):
        s += 1
        while not is_prime(s):
            s += 1
        return s

    def next_e(e):
        e -= 1
        while not is_prime(e):
            e -= 1
        return e

    s = 3
    e = N-3 if is_prime(N-3) else next_e(N-3)
    while s <= e:
        ssum = s + e
        if ssum == N: return s, e
        elif ssum > N: e = next_e(e)
        elif ssum < N: s = next_s(s)
    return 0, 0


while True:
    N = int(input())
    if not N: break
    s, e = check(N)
    ret = "Goldbach's conjecture is wrong." if not (s or e) else f'{N} = {s} + {e}'
    print(ret)

에라토스테네스의 체와 소수 판정, 그리고 문제에는 명시되어 있지 않지만 투포인터 알고리즘을 사용하였다. 에라토스테네스의 체처럼 배열을 따로 만들어서 소수를 만들지 않고, 소수를 판단하는 함수를 작성해서 매번 소수 판단을 해주었다.

가장 작은 홀수 소수인 3을 s로 두고, N-3보다 같거나 작은 소수를 e로 설정한다. 두 값의 합이 N일 때까지 s와 e를 좁혀주는 작업을 하는데, 우선 s와 e의 값 합이 N보다 크다면 e를 줄여 합을 줄여주고, s와 e의 값 합이 작다면 s를 키워 합을 키워준다.

이 과정을 반복하며 합을 맞춰간다.

결과

맞았습니다!!

로직이 모두 틀린 점이 없는 것 같은데 자꾸 ‘틀렸습니다.’ 결과가 나와서 뭐가 문제인지 계속 검토했는데, 알고보니 짝수를 이루는 두 홀수 소수 값이 같은 경우를 고려하지 않아 s < e 로만 따졌던 것이다.

이를 s <= e 로 수정해 제출하니 ‘맞았습니다.’ 결과가 나왔다.

모범답안

출처

import sys

prime_numbers = [True for i in range(1000001)]
for i in range(2, int(1001)):
    if prime_numbers[i]:
        for j in range(i*2, 1000001, i):
            prime_numbers[j] = False

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    for i in range(3, len(prime_numbers)):
        if prime_numbers[i] and prime_numbers[n-i]:
            print(f'{n} = {i} + {n-i}')
            break

연산시간이 1/4정도인 풀이를 분석해보려 한다. 미리 배열을 만들고, 소수를 판단하면 이후의 해당 소수의 곱들에 대해 소수가 아니라고 체크하는 에라토스테네스의 체 알고리즘을 사용하셨다. 그리고 골드바흐의 추측이 틀린 경우는 특별히 고려하지 않은 듯 하다.

이전에 에라토스테네스의 체를 사용했을 때는 소수 판단 함수를 매번 돌려 확인했는데, 이 문제 같은 경우 테스트케이스가 최대 10만으로 많고, 범위도 100만으로 꽤나 크기 때문에 에라토스테네스의 체를 미리 만들어 확인하는 것이 더 효율적이었던 것으로 보인다.