[백준 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."을 출력한다.

 

---

문제의 핵심은 주어진 수보다 작은 소수 두개의 합으로 주어진 수를 만들 수 있는지 판별하는 것이다

먼저 소수를 구하기 위한 코드를 직관적으로 작성하고 시간을 줄이기 위해 제곱근을 사용했다

for i in A:
    Count = 0
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            Count += 1
    if Count==0:
        ans+=1

 

X의 약수는 X의 제곱근 범위에 존재하기에 2~(X-1)의 수들로 X를 나누어보며 약수를 판단하기보다 2~sqrt(X)의 수들로 X를 나누어보며 판단하면 시간을 줄일 수 있다

예를 들어 12약수는 1, 2, 3, 4, 6, 12로 곱셈으로 표현하면 (1*12, 2*6, 3*4) | (4*3, 6*2, 12*1)로 표현 가능하다

앞의 수가 12의 제곱근을 정수내림한 3을 넘어가면 반대쪽은 대칭을 이루는 것을 볼 수 있다

 

하지만 위와 같은 방법으로 주어지는 n보다 작은 소수 i를 구하고 n-i도 소수인지 판단하여 출력하는 코드는 시간초과가 난다

 

따라서 특정 범위 내의 소수들을 더 빠르게 구할 수 있는 에라토스테네스의 체를 사용했다

#에라토스테네스 체
PrimeArr = [True for i in range(1000001)]
PrimeArr[0],PrimeArr[1] = False,False

for i in range(2,1000001):
    if PrimeArr[i]:
        for j in range(i+i,1000001,i):
            PrimeArr[j]=False

 

에라토스테네스의 체는 N보다 작은 소수들을 구해야 할 때 자주 사용된다

i를 2~N까지 증가시키며 i의 배수를 False처리하여 남는 True들을 소수 조건에 만족시킨다

시간복잡도는 O(Nlog(logN))으로 아주 짧은 편이다

 

위 과정을 거쳐 PrimeArr배열엔 소수인 인덱스에만 True가 들어있게 되고 이 소수배열을 활용하여 다음과 같이 풀어냈다

while True:
    r = int(sys.stdin.readline())
    if r==0:
        break
    flag = 0
    for i in range(3,r,2):
        if PrimeArr[i] and PrimeArr[r-i]:
            print(r,"=",i,"+",r-i)
            flag = 1
            break
    if (not flag):
        print("Goldbach's conjecture is wrong.")