[BOJ/Python] 6588_골드바흐의 추측

문제 출처: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."을 출력한다.

예제 입력 1

8
20
42
0

예제 출력 1

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

---

풀이

 

에라토스테네스의 체를 이용하여 소수들의 리스트를 구하고, 입력받은 수를 홀수인 소수(2를 제외한 나머지 소수)의 합으로 나타낼 수 있는지 확인하여 문제를 풀었다.

 

코드는 다음과 같다.

 

import sys
import bisect
 
n_list = [True for _ in range(1000001)]
n_list[0] = False
n_list[1] = False
 
prime_numbers=[]
 
for i in range(3,1000001,2):
    if n_list[i]==True:
        prime_numbers.append(i)
        for j in range(i,1000001,i):
            n_list[j]=False
 
while True:
    n = int(sys.stdin.readline())
    if n==0:
        break
 
    for i in prime_numbers:
        if i>n:
            print("Goldbach's conjecture is wrong.")
            break
        else:
            if bisect.bisect_left(prime_numbers,n-i)!=bisect.bisect_right(prime_numbers,n-i):
                print(n,"=",i,"+",n-i)
                break

 

• 우선 홀수인 소수를 구해야 하므로, 소수 판별을 3부터 1,000,000까지 홀수에 대해서만 처리했다.
• prime_numbers 에는 홀수이면서 소수인 수가 들어있게 된다.
• 이제 n을 입력받았을 때, 이 수를 두 소수의 합으로 나타낼 수 있는 경우를 찾아야 한다.
• 여기서 n = a + b 일 경우, b-a의 값이 가장 큰 결과를 출력하라고 하였으므로, 가능한 경우 중 a가 가장 작은 소수여야 한다.
• 따라서 a + b가 n이 되는 경우를 a의 값을 늘려가면서 찾고, 찾게 되면 break를 이용하여 반복문을 종료한다.
• 다시 돌아와서 for문을 살펴보면, 소수들은 에라토스테네스의 체를 이용하여 prime_numbers에 append 될 때, 오름차순으로 저장되므로 작은 소수부터 차례로 탐색하게 된다.
• 오름차순으로 정렬되어 있으므로, 따로 정렬할 필요 없이 binary search를 이용하여 (n-i)의 값이 prime_numbers에 존재하는지 확인한다.
• 만약 소수의 값이 n보다 크다면, n을 소수의 합으로 표현할 수 없으므로 문자열을 출력한다.

---

---- 수정 : 2023-02-10 ----

6588번 - 골드바흐의 추측 문제가 재채점 되었습니다.  (재채점 이유: 데이터 추가) 13:51

문제가 재채점되면서, 시간초과 판정을 받게 되었다.

그러면서 기존의 작성했던 코드를 다시 살펴보고 코드를 수정하였다.

수정한 부분들은 다음과 같다.

1. 우선 소수 i에 대하여 n-i를 빠르게 구하기 위하여 이진탐색을 이용하였지만, 굳이? 라는 생각이 들었다.
2. 리스트의 경우 어떠한 원소가 리스트에 존재하는 지 확인하려면 O(n)의 시간복잡도가 든다. 그래서 이진탐색을 이용하여 조금이라도 단축하려고 했었던 것 같다.
3. 하지만, 파이썬의 경우 어떤 소수가 존재하는 지 확인하는 경우라면 set 또는 dictionary 자료형을 이용하면 O(1)의 시간복잡도로 확인 가능하다.
4. 따라서 소수를 저장하는 prime_numbers를 set 또는 dictionary로 바꾸는데, set의 경우 순서가 없기때문에 b-a의 값이 가장 큰 결과를 보장할 수 없다.
5. 따라서 딕셔너리 자료형을 이용하여 코드를 수정하였다.

코드는 다음과 같다.

 

import sys
 
n_list = [True for _ in range(1000001)]
n_list[0] = False
n_list[1] = False
 
prime_numbers=dict()
 
for i in range(3,1000001,2):
    if n_list[i]==True:
        prime_numbers[i]=0
        for j in range(i,1000001,i):
            n_list[j]=False
 
while True:
    n = int(sys.stdin.readline())
    if n==0:
        break
 
    for i in prime_numbers.keys():
        if (n-i) in prime_numbers:
            print(n,"=",i,"+",n-i)
            break
        if i>n:
            print(i,n)
            print("Goldbach's conjecture is wrong.")