[BOJ] 6588번 - 골드바흐의 추측

---

문제설명

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

6588번: 골드바흐의 추측

사고과정

• 우선 n = a + b 가 되는 경우의 수를 모두 살펴보지 않아도 된다. 이 때,  b - a 가 가장 큰 것만 출력하면 되므로  a = (n // 2)가 될 때까지의 n = a + b 연산만 되는 경우를  확인하면 된다. 그리고 가장 먼저 n = a + b가 되는 조건이 만족했을 때가 b - a가 가장 클 때의 연산이다. 따라서 최초에 n = a + b가 되게 되면 바로 break하면 된다.(물론 a, b가 모두 홀수이고 모두 소수라는 조건 만족할 때!)
• 처음에 a , b 모두 소수인 것을 판별하는 코드를 짤 때, 특정 수가 소수인지 아닌지 편별하는 알고리즘을 짰지만 시간초과가 발생했다. 왜냐하면 n이 최대 100만까지 나올 수 있기 때문이다. 이걸 어떻게 빠르게 할 수 있을까 하다가 에라토스테네스의 체를 활용해서 애초에 먼저 0부터 100만까지 소수 판별을 한 번 해놓고 n이 계속 입력될 때 마다 그 판별된 리스트 인덱스를 참조하면 된다. 마치 다이나믹 프로그래밍 처럼! 미리 계산해놓고 나중에 그값을 활용하는 식이다.

풀이

import math
import sys
input = sys.stdin.readline

# 0부터 100만까지 소수 판별 배열
array = [True] * (int(1e6) + 1)
array[0] = array[1] = False

for i in range(2, int(math.sqrt(1e6)) + 1):
    if array[i]:
        j = 2
        while i * j <= int(1e6):
            array[i*j] = False
            j += 1

while True:
    n = int(input())
    if n == 0:
        break
    # n = a + b
    for i in range(3, n//2 + 1):
        a, b = i, n - i
        # 두 숫자 모두 홀수여야 함
        if a % 2 != 0 and b % 2 != 0:
            # 두 숫자 모두 소수여야 함
            if array[a] is True and array[b] is True:
                print(f"{n} = {a} + {b}")
                break