[Math] 9020번 - 골드바흐의 추측(39일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#에라스토테네스의 체
def prime_number(n):
  number_list = [True] * (n+1)
  return_list = []
  for i in range(2, n+1):
    if (number_list[i] == True):
      return_list.append(i)
      for j in range(2*i, n+1, i):
        number_list[j] = False
  return return_list
#가장 차가 작은 두 소수 탐색 함수
def sosu(prime):
  global n
  #n//2 범위에서 가장 큰 소수가 위치하는 인덱스 탐색
  idx = max([i for i in range(len(prime)) if prime[i] <= n//2])
  #해당 인덱스부터 왼쪽으로 소수 a를 탐색
  for i in range(idx, -1, -1):
    #해당 인덱스부터 오른쪽으로 소수 b를 탐색
    for j in range(idx, len(prime)):
      #두 소수의 합이 n이면
      if(prime[i] + prime[j] == n):
        #해당 소수 반환
        return [prime[i], prime[j]]

t = int(input())

for _ in range(t):
  n = int(input())
  #n을 입력값으로 가장 차가 작은 두 소수 탐색
  result = sosu(prime_number(n))
  #출력
  print(f'{result[0]} {result[1]}')

#인사이트
#탐색 문제는 탐색지점의 설계를 얼마나 효율적으로 할 것인가
#그리고 문제 요구사항을 적은 시간복잡도로 충족시킬 수 있는 탐색지점을 설계하는 것이 중요함

#코드 실행 시간 단축
import sys
input = sys.stdin.readline
#반복 횟수 입력
t = int(input())

#소수 생성
def prime_number(n):
  number_list = [True] * (n+1)
  return_list = []
  for i in range(2, n+1):
    if (number_list[i] == True):
      return_list.append(i)
      for j in range(2*i, n+1, i):
        number_list[j] = False
    else:
      continue
  return return_list


for _ in range(t):
  #짝수 n 입력
  n = int(input())
  #소수 저장하는 변수
  prime = prime_number(n)
  #n을 만드는 소수 합 저장하는 변수
  result = []
  #소수 차이 최대값 저장
  prime_max = 1000001
  #1~n//2 소수까지 반복
  for i in range(len(prime)):
    if(prime[i] > n//2):
      break
    #n보다 작은 가장 큰 소수부터 2까지 반복
    for j in range(len(prime)-1, -1, -1):
      #두 소수의 합이 n이면
      if(prime[i] + prime[j] == n):
        #두 소수의 차가 최대값보다 작으면
        if(prime[j] - prime[i] <= prime_max):
          #결과 list에 추가하고
          result.append([prime[i], prime[j]])
          #소수 차 최대값에 두 소수의 차 저장
          prime_max = prime[j] - prime[i]
        break
      else:
        continue
  #가장 소수 차가 작은 두 소수 출력 (가장 뒤에 있는 소수)
  print(f'{result[-1][0]} {result[-1][1]}')

#인사이트
#문제 번호 똑바로 보자..
#탐색은 인덱스 설계가 가장 중요!