[백준] 9020 골드바흐의 추측

문제출처] https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

---

문제요약

골드바흐의 추측을 구현

풀이

먼저 4 ≤ n ≤ 10,000 인 범위에서 소수를 판별하기 위해 에라토스테네스의 체를 이용한다. 에라토스테네스의 체는 소수인 수의 배수들은 소수가 아님을 이용한다. 

list_number = [True for _ in range(10001)]
for i in range(2, 10001):
  if list_number[i]:
    for j in range(i*i, 10001, i):
      list_number[j] = False

---

소수가 판별되었으면 짝수(Even)를 입력받아서 가장 작은 소수인 2부터 짝수의 절반까지 for문을 돈다. 만약 i 가 소수이고 짝수 - i 도 소수이면 골드바흐의 파티션이 된다. 골드바흐의 파티션이 여러 개인 경우에 i 가 작은 수부터 증가하므로 두 소수의 차이가 가장 작은 파티션이 결과값에 저장된다. 

for _ in range(n):
  even = int(input())
  result = []
  for i in range(2, even//2+1):
    if list_number[i] and list_number[even-i]:
      result = [i, even-i]

---

소스코드는 Python 3으로 작성되었습니다.

list_number = [True for _ in range(10001)]
for i in range(2, 10001):
  if list_number[i]:
    for j in range(i*i, 10001, i):
      list_number[j] = False

n = int(input())

for _ in range(n):
  even = int(input())
  result = []
  for i in range(2, even//2+1):
    if list_number[i] and list_number[even-i]:
      result = [i, even-i]

  print(result[0], result[1])