[Python] 6588 - 골드바흐의 추측 (실버1) : 에라토스테네스의 체

1. 문제 설명

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

6588번: 골드바흐의 추측

오일러..굉장히 존경스러운 수학자시긴 하지만 시험 기간에는 별로 반갑지 않은..ㅠㅠㅠ

---

2. 아이디어

소수를 구하는 가장 빠른 방법이다. (아마도..?)

"소수를 구하는 문제 -> 에라토스테네스의 체"라고 머리에 쑤셔넣어놓아야 할 정도로 중요하다.

나도 간만에 봤더니 잊어 먹어서 다시 공부했지만 ㅎㅎ.

---

에라토스테네스의 체

이 방법을 사용하지 않으면..시간 초과에서 벗어나기가 상당히 힘들 것이다.

특히나 안 그래도 속도가 느린 Python으로 문제를 해결하려면 불가능하다.

에라토스테네스의 체에서 핵심은 우선 소수를 전부 구해놓는 것이다.

N 크기만큼의 리스트를 True로 채운 뒤,

2의 배수를 모두 False로 바꾸고,

3의 배수를 모두 False로 바꾸고

그렇게 쭉 하다보면 결국 끝까지 True인 인덱스가 곧 소수값이 된다.

 

그러면 다시 for문을 돌려서 i번째 인덱스와 n-i번째 인덱스의 합이 n이 되는 소수가 존재함을 증명하면 끝난다.

내 기억이 맞다면 문제 조건에서 준 6 ≤ n ≤ 1000000 범위 내에서는 골드바흐의 추측이 무조건 성립하여

"Goldbach's conjecture is wrong."를 출력하는 조건을 걸지 않아도 된다는 말을 들었던 것 같다.

 

---

3. 코드

def get_decimal(n):
    decimal = [True for i in range(n)]
    for i in range(2, 1001):
        if decimal[i]:
            for k in range(i + i, n, i):
                decimal[k] = False
    return decimal

def solution():
    decimal = get_decimal(1000001)
    while True:
        n = int(input())
        if n == 0:
            break
        
        flag = 0
        for i in range(3, len(decimal)):
            if decimal[i] and decimal[n - i]:
                print(f"{n} = {i} + {n - i}")
                flag = 1
                break
        if flag == 0:
            print("Goldbach's conjecture is wrong.")

solution()