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

 

 

 

 

 

---

 

 

 

💻 코드

 

 

import sys

prime_list = [True for i in range(1000001)]

for i in range(2, int(1000000**0.5) + 1):
    for j in range(i + i, 1000001, i):
        prime_list[j] = False

while True:
    n = int(sys.stdin.readline())

    if (n == 0):
        break

    for i in range(3, len(prime_list)):
        if prime_list[i] and prime_list[n - i]:
            print(n, "=", i, "+", n - i)
            break

 

 

 

 

 

 

📝 풀이

 

 

이 문제는 이전에 풀었던 소수 구하기 문제에서 응용된 버전으로, 입력한 짝수를 두 홀수 소수의 합으로 나타내는 문제이다. 처음에는 1929번 소수 구하기 문제에 작성한 함수를 가져와 소수 리스트를 만들어 리스트를 탐색하며 두 홀수 소수의 합을 찾아내는 방식으로 풀었는데 역시나 시간 초과가 걸렸다. 이 문제를 해결하기 위해서는 소수를 구하는 방법을 바꿔야 했다. 소수를 찾는 알고리즘인 에라토스테네스의 체를 이용하여 풀어서 해결했다.

 

 

 

에라토스테네스의 체란?

 

소수를 찾는 알고리즘으로 순서는 다음과 같다.

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

 

 

 

 

 

 

↓ 에라토스테네스의 체를 이용하여 소수 찾는 알고리즘 구현하기

 

 

prime_list = [True for i in range(1000001)]

for i in range(2, int(1000000**0.5) + 1):
    for j in range(i + i, 1000001, i):
        prime_list[j] = False

 

 

 

시간 복잡도를 줄이기 위해서 입력하는 숫자마다 소수를 구하지 않고 미리 최대 입력 케이스인 1000000까지의 소수 리스트를 만들어두고 이 리스트를 활용해야한다. 소수를 찾을 때는 앞서 말했던 에라토스테네스의 체를 이용하여  for문을 통해 i번째일 때 자기 자신 i를 제외한 i의 배수들의 인덱스를 모두 false로 만들면서 이를 반복하고, 1000000까지 돌면 남은 True 값을 가진 인덱스는 소수 리스트가 된다. 이 리스트를 이용하여 형식에 맞게 출력하면 된다.

 

 

 

 

다음은 이 문제를 풀면서 코드를 이해하기 위해 필기했던 노트이다. (글씨를 좀 날려적은 것 같긴하지만 참고용으로 올려둔다.)

 

 

 

 

 

 

※ 참고

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전