[Python] 백준(BOJ) 6588번: 골드바흐의 추측

문제

6588번: 골드바흐의 추측

풀이

에라테스토스트의 체를 활용해서 최대값인 1000000까지의 소수 여부 모두 구하고,

그 후에 무한루프를 통해서 0이 들어오기 전의 값들에 대해 판별을 해주면 된다. 

판별하는 방법은 가장 작은 소수(a)부터 하나씩 n-a도 소수인지 확인을 하면 되는데,

 

list에서 in을 사용할 경우 시간복잡도가 O(n) 이 되기 때문에 따로 소수 리스트를 만들지 않고,

arr을 그대로 사용해서 소수인지 아닌지 확인하는 시간을 O(1)으로 줄였다.  

import sys

num = 1000001
arr = [True for _ in range(num)]
for i in range(2, int((num-1)**0.5)+1):
    if arr[i]:
        for k in range(i+i, num, i):
            arr[k] = False

while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break

    flag = 0

    for a in range(3, len(arr)):
        if arr[a] and arr[n-a]:
            print(str(n) + " = " + str(a) + " + " + str(n-a))
            flag = 1
            break
    if flag == 0:
        print("Goldbach's conjecture is wrong.")