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

• Problem Link : https://www.acmicpc.net/problem/6588

문제

입력으로 들어온 테스트 케이스에 대해서 두 소수의 합으로 나타낼 수 있는지 구하여라, 이 때 두 소수의 차이가 가장 큰 경우를 결과로 출력한다. 만약 소수의 합으로 결과를 나타낼 수 없다면 "Goldbach's conjecture is wrong."을 출력한다.

입력

• 테스트 케이스가 주어진다.
• 마지막 줄에는 0이 하나 주어진다.

출력

• 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다.
• 만약 a, b가 없다면 "Goldbach's conjecture is wrong."을 출력한다.

풀이

전형적인 소수 찾기 문제이다. 소수 찾기는 에라토스테네스의 체를 쓴다고 누누히 언급했다. 에라토스테네스의 체에 대한 설명은 이 문서를 참고하자. 그렇다면 동일하게 에라토스테네스의 체를 쓰는 문제를 왜 또 글을 작성하냐면 기존의 방식보다 훨씬 간단하게 체를 구현해서 소수를 구하는 방식을 찾았기 때문이다.

기존 에라토스테네스의 체

def eratosthenes_sieve(N):
    IsPrime[0] = IsPrime[1] = False
    for i in range(2, int(N**0.5) + 1):
        for j in range(i * 2, N + 1, i):
            IsPrime[j] = False
    prime = []
    for i in range(N + 1):
        if IsPrime[i]:
            prime.append(i)

    return prime

수정한 에라토스테네스의 체

isPrime = set(i for i in range(2, M))
for i in range(2, int(M**0.5 + 1)):
    if i in isPrime:
        isPrime.difference_update(range(i * i, M + 1, i))

코드의 길이, 실행 시간 모두 수정한 버전이 더 좋은 성능을 보인다. 실행 방식을 설명하자면 아래와 같다.

1. isPrime을 사용하는건 기존 방식과 동일하지만 이 때 True, False가 아니라 2부터 M까지 모든 정수를 집합에 저장한다.
2. i가 isPriem안에 존재한다면 i의 배수를 모두 지워야한다. 이 때 원래는 반복문으로 i의 배수부터 하나씩 지워나갔지만 그렇게 할 필요 없이 i*i부터 M까지의 정수 리스트를 이용해 기존 isPrime 집합에 difference_update 함수를 사용한다.
3. 해당 과정을 기존과 동일하게 $M^{0.5}$ + 1 까지 반복한다.

range의 반환이 list형이라고 생각할 수 있는데 실제로는 마땅히 range 객체라고 불러야한다. 그 성질은 'iterable'한 정수 원소를 가진 list 유사의 객체라고 할 수 있다.

• 파이썬에서 list, dict, set, str, bytes, tuple, range 등은 iterable한 객체입니다.

difference_update 함수 : 두 Set에서 공통 요소, 교집합를 제거한다
- 반환값은 따로 없음

위와 같이 개선된 에라토스테네스의 체를 소개하기 위해 해당 글을 작성했다.
체를 사용해 소수를 모두 구했다면 이후 두 정수를 구하는 건 간단하게 구현가능하다. prime을 앞에서 꺼내면서 n - prime의 값이 prime안에 존재하다면 바로 출력하고 break해주면 된다.

prime, n-prime을 구하면 그 차이는 n - ( 2 * prime )이므로 가장 먼저 찾은 prime이 가장 작은 prime이고 해당 값이 차이가 가장 커지는 값이다.

• prime을 앞에서부터 꺼내기 때문이다.

코드

import sys

input = sys.stdin.readline
M = 10**6

isPrime = set(i for i in range(2, M))
for i in range(2, int(M**0.5 + 1)):
    if i in isPrime:
        isPrime.difference_update(range(i * i, M + 1, i))

while True:
    n = int(input())
    if n == 0:
        break

    for prime in isPrime:
        if n - prime in isPrime:
            print(n, "=", prime, "+", n - prime)
            break

    else:
        print("Goldbach's conjectrue is wrong.")