[백준_6588] 골드바흐의추측 _ python

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

6588번: 골드바흐의 추측

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

문제 해결

경우의 수가 100만까지 주어지기 때문에  에라토스테네스의 체 알고리즘을 활용하여

100만 이하의 수의 primelist를 먼저 초기화시켜놓고 2개의 소수를 찾으면 된다.

*primelist에서 오름차순으로 값을 빼내며 빼낸 값에 대응되는(하나일 수밖에 없음) 값이 소수인지 판별 후 

소수일 경우에  a, b의 차이가 최대인 값이 구해지게 되기 때문에 다른 경우는 더 뽑지 않게 break로 마무리해주었다.

 

기존에는 while문으로 구현한 에라토스테네스의 체를 썼는데 이번엔 위키피디아에 실려있는 코드를 사용해 보았다.

개인적으로 while문보다 for문을 사용하는 게 간결하고 직관적이라 소수 리스트를 초기화하는 상황에서는 앞으로 이 형식을 사용할 것 같다.

import math
arr = [True for i in range(1000001)]
primelist = []
def prime_list(x):
    global primelist
    for i in range(2,int(math.sqrt(1000000))+1):
        if arr[i] == True:
            for j in range(i+i,1000001,i):
                arr[j] = False
    primelist = [i for i in range(2,1000001) if arr[i]==True]
prime_list(1000000)
#print(primelist)    #소수 리스트를 구하고
while True:
    n = int(input())
    if not n:
        break       
    for i in primelist:
        if arr[n-i] :
            print('%d = %d + %d' %(n,i,n-i))
            break