백준 boj 6588 - 골드바흐의 추측 (파이썬, python)

https://www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

 

 

6 이상의 짝수는 두 개의 소수의 합으로 이뤄진다는 골드바흐의 추측을 구현하는 문제였다.

입력받은 숫자와, 두 개의 소수를 한 번에 출력해주면 되는 문제였다.

 

소수의 경우 에라토스테네스의 체를 사용했는데,

에라토스테네스 체를 구현하는 두 방식을 비교하여 조금 더 빠른 방식을 확인하였다.

 

EOFError를 통해 끝까지 입력 받을 수 있게 했고,

input 값이 0이라면 프로그램을 종료하게 했다. (문제 푸는 것보다 이게 오래 걸렸다...)

만약 input 값이 골드바흐의 추측에 부합하지 않는 경우라면 지정된 문자열을 출력해주었다.

 

 

code

import sys

dp = [1] * (1000000 + 1)
dp[0] = 0
dp[1] = 0

for i in range(2, 1001):
    if dp[i]:
        for j in range(i * i, 1000001, i): # i의 배수를 지워 나감
            dp[j] = 0

# 같은 에라토스테네스의 체를 구하는 코드이지만, 위와 비교하면 300ms 정도 느림
# for i in range(2, max_val + 1):
#     j = 2
#     while i * j <= max_val:
#         dp[i * j] = 0
#         j += 1

def check_goldbach(n):
    for i in range(2, n):
        if dp[i] and dp[n - i]: # e.g. 20 = 3 (i) + 17 (n - i)
            print(f'{n} = {i} + {n - i}')
            return 0 # 0을 return 하면서 지정된 문자열을 출력하지 못하게 함
    return 1 # 골드바흐의 추측에 부합하지 않으므로 지정된 문자열을 출력

while 1:
    try:
        n = int(sys.stdin.readline())
        if n == 0: # 이거 안해주면 런타임 에러 남...
            break
        if check_goldbach(n): # return 값에 따라 아래 문자열 출력
            print("Goldbach's conjecture is wrong.")
    except EOFError:
        break