백준 9020 골드바흐의 추측 / python

문제 : 9020

풀이 point

입력 받은 짝수 n에 대해 x+y가 n이 되고, x, y가 소수이며 답이 여러개일 경우 x-y가 가장 최소가 되는 값을 구해야한다.

완전탐색을 통해 n을 만들 수 있는 모든 값에 대하여 소수인지 판별하고 두 수를 구한다.
이때 x-y가 가장 최소가 되야한다는 조건에 따라 n/2, n/2부터 시작하여 -1, +1을 하면서 찾아나가면 된다.

소수를 판별하기 위해서는 1부터 n사이의 모든 수를 나누어 봄으로써 알 수 있다. 이 문제에서는 해당 방식으로 해결하여도 시간초과의 문제는 존재하지 않는다. 다만, 루트 값을 통해 소수인지 판별하는
"에라토스테네스의 체" 방식이 존재한다.

풀이 코드

T = int(input())

def check(num):
  for i in range(2, num):
    if num%i == 0:
      return False
  return True


for _ in range(T):
  n = int(input())

  n1, n2 = n//2, n//2

  while True:
    if check(n1) and check(n2):
      print(n1, n2)
      break
    else:
      n1 -= 1
      n2 += 1