[파이썬] 백준 6588 번 : 골드바흐의 추측

출처 : www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

우선, 에라토스테네스의 체를 이용하여 a라는 배열에 소수를 넣고 prime이라는 곳에 소수를 표시해 놓았다.

prime 배열을 이용하여 n - i가 소수 인지를 판별하고 소수라면 답을 출력하도록 하였다.

 

import sys
 
MAX = 1000000
 
prime = [0]*(MAX+1)
a = []
 
prime[0] = prime[1] = True
 
for i in range(2,MAX+1):
    if not prime[i]:
        a.append(i)
        j= i+i
        while j<=MAX:
            prime[j] = True
            j += i
 
while 1:
    n = int(sys.stdin.readline().strip('\n'))
    if n == 0:
        break
 
    for i in a:
        if prime[n-i] == False:
            print("{} = {} + {}".format(n,i,n-i))
            break