(Python) 백준 6588번 - 골드바흐의 추측

문제 링크: https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

풀이

문제를 해결하기 위한 기본적인 아이디어는 에라토스테네스의 체이다.

우선 가장 홀수 중 가장 작은 소수인 3부터 시작해서 소수인지 검사하고, 만약 그 수(x)가 소수라면 n-x도 소수인지 체크를 한다. 이 모든 체크가 통과되면 n = x + n-x를 출력하면 된다.

import sys

MAX_NUM = 1000001 # N의 최대값
arr = [True] * (MAX_NUM + 1) # 일단 모두 소수라고 가정
arr[0] = False # 0은 소수가 아님
arr[1] = False # 1은 소수가 아님


def check_prime_number(): # 에라토스테네스의 체를 사용하여 소수인지 판별하는 메서드
    for _i in range(2, int((MAX_NUM - 1 ** 0.5) + 1)): # 2부터 에라토스테네스의 체 적용
        if arr[_i]: # 애초에 소수가 아닌 것으로 판명된 것을 체크할 필요가 없음
            for _j in range(2, (MAX_NUM // _i) + 1): # 2배부터 최대 수가 되기 전까지의 배수들은
                arr[_i * _j] = False # 소수가 아님
                

check_prime_number()
while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break

    cond = False
    for i in range(3, int(N / 2) + 1, 2):
        cond = arr[i] and arr[N - i] # i와 N-i가 모두 소수인지 검증
        if cond: # 둘 다 소수면
            print(f"{N} = {i} + {N - i}")
            break
    if cond is False: # 최종적으로 소수를 만들 수가 없으면
        print("Goldbach's conjecture is wrong.")

이렇게 하면 백준 기준 PyPy3에선 통과가 된다. 하지만 Python 3 컴파일러로 실행 시에도 통과하고 싶었다. 그래서 아래와 같이 2 이상의 소수는 모두 홀수이므로 소수들을 체크하는 메서드의 for문에서 짝수를 스킵하도록 2씩 증가하도록 하였다.

import sys

MAX_NUM = 1000001
arr = [True] * (MAX_NUM + 1)
arr[0] = False
arr[1] = False
arr[2] = False


def check_prime_number():
    for _i in range(3, int((MAX_NUM - 1 ** 0.5) + 1), 2): # 홀수만 체크하면 되기에 2씩 증가하도록 변경
        if arr[_i]:
            for _j in range(2, (MAX_NUM // _i) + 1):
                arr[_i * _j] = False


check_prime_number()
while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break

    cond = False
    for i in range(3, int(N / 2) + 1, 2):
        cond = arr[i] and arr[N - i]
        if cond:
            print(f"{N} = {i} + {N - i}")
            break
    if cond is False:
        print("Goldbach's conjecture is wrong.")