백준 9020번 : 골드바흐의 추측 (Python)

출처 : https://www.acmicpc.net/problem/9020

t = int(input())
sol = []

# 에라토스테네스의 체로 n 이하 소수로 이루어진 리스트 생성
for i in range(t) :
  n = int(input())
  check = [True] * (n+1)
  check[0] = check[1] = False
  root_n = int(n**(1/2))

  for i in range(2, root_n+1) :
    if check[i] == True :
      for j in range(i*2, n+1, i) :
        check[j] = False

  prime = []
  for i in range(2, n+1) :
    if check[i] == True :
      prime.append(i)

# 소수 리스트를 두 개로 분리
  for i in prime :
    if i >= n/2 :
      prime1 = prime[prime.index(i): ]
      prime2 = prime[ :(prime.index(i)+1)][::-1]
      break

# n의 골드바흐 파티션 구하기
  for i in prime1 :
    stop = False
    for j in prime2 :
      if i + j == n :
        sol.append([j, i])
        stop = True
        break
      if i + j < n :
        break
    if stop == True :
      break

for i in sol :
  print(*i)

문제를 크게 두 단계로 나누어 풀 수 있다.

 

1. n 이하 소수로 이루어진 리스트 생성

에라토스테네스의 체를 이용한다.

길이 n+1 인 리스트(check)를 만들고, 리스트의 인덱스에 해당하는 숫자가 소수면 True, 합성수면 False를 저장하는 것이 목표이다. 

현재 check에 True로 남아있는 값 중 인덱스 번호가 가장 낮은 수는 소수(ex 2)이므로 남기고, 그 소수의 배수(ex 4, 6, 8 ...)에 해당하는 인덱스의 값는 모두 False로 바꿔주면 최종적으로 인덱스 번호가 소수인 값들만 True로 남는다.

이 때 체로 거르는 연산은 n의 제곱근까지만 해도 충분하다.

 

2. n의 골드바흐 파티션 구하기

앞서 구한 소수 리스트를, n/2 보다 큰 소수 중 가장 작은 소수를 기준으로 둘로 나눈다.

n이 20일 때를 예로 들어 보면, 20 이하 소수 [2, 3, 5, 7, 11, 13, 17, 19]의 리스트를

1번 - [11, 13, 17, 19]

2번 - [11, 7, 5, 3, 2]

이렇게 나눠준다.

가능한 n의 골드바흐 파티션이 둘 이상인 경우 두 소수의 차이가 가장 작은 것을 출력해야 하기 때문에, n/2에 가장 가까운 소수 쌍을 선택해야 한다.

즉, 둘로 나눈 리스트의 앞에서부터 합이 n이 되는지 체크하면 된다.

예시처럼 n이 20인 경우에는 ,

1번 리스트의 11부터 2번 리스트의 11, 7, 5 ... 순서대로 매칭하다 합이 20보다 작아지면 이후의 합도 20보다 작아지므로

1번 리스트의 다음 소수 13으로 넘어간다.

다음으로 13과 2번 리스트의 11, 7, 5... 순서대로 매칭하다 보면 13과 7의 합이 20이 되어 정답이다.