문제

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

---

접근

1. NUM 미만 모든 소수를 찾는다.
   • NUM == 16 ) sosu_list = [2, 3, 5, 7, 11, 13]
2. 2 <= x <= 2/NUM, 2/NUM <= y <= NUM 을 만족시키는 소수의 집합을 찾고 x는 뒤집는다.

3. i=0, j=0 일 때, x[i]+y[j] < NUM 이라면 j를 1씩 증가시키다가 NUM보다 커지면 j를 0으로 초기화 시키고 i를 1 증가시킨다.

---

코드

📌 python

import sys
input = sys.stdin.readline

CASE = int(input())

for _ in range(CASE) :

    NUM = int(input())
    
    # 소수생성
    sosu = [True] * (NUM)
    
    for num in range(2, int(NUM**0.5)+1) :
        if sosu[num] :
            for i in range(num*num, NUM, num) :
                sosu[i] = False

    
    standard_num = int(NUM/2)
    x = [] # NUM/2 이하 소수 리스트
    y = [] # NUM/2 이상 소수 리스트

    for i in range(2, len(sosu)) :
        if sosu[i] :
            if i <= standard_num :
                x.append(i)
                if i == standard_num :
                    y.append(i)
            else :
                y.append(i)

    x.reverse()
    
    i = 0
    j = 0

    while( x[i]+y[j] != NUM ) :
        if x[i]+y[j] < NUM :
            j += 1
        elif x[i]+y[j] > NUM :
            j = 0
            i += 1

    print(f"{x[i]} {y[j]}")