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

골드바흐의 추축은 아래와 같이 설명된다.

• 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
• 위의 문장에 3을 더하면
• 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
• 증명이 되어있지 않아 추측
• 하지만 10^18이하에서는 참인 것이 증명되어 있다.

100만 이하의 짝수가 들어왔을 때, 두 소수의 합으로 표현할 수 있는지를 알아보는 문제

 

Example)

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

6588번: 골드바흐의 추측

 

Solution)

MAX = 1000000
check = [0]*(MAX+1)
prime = []
check[0] = check[1] = True

for i in range(2, MAX+1):
    if not check[i]:
        prime.append(i)
        j = i+i
        while j <=MAX:
            check[j] = True
            j += i
prime = prime[1:]
while True:
    n = int(input())
    if n == 0: 
        break

    for p in prime:
        if check[n-p] == False:
            print("{0} = {1} + {2}".format(n,p, n-p))
            break