백준 9020 골드바흐의 추측

계획

• 주어진 수보다 작은 소수를 모두 찾아 리스트에 넣고,
• 리스트 순회하면서 (주어진 수 - 값)이 리스트에 있는지 확인
• 에라토스테네스 체 구현해보기

배운점

• 에라토스테네스의 체를 제곱근까지만 구하기
• 여러 번 계산하지 말고, 문제에서 주어지는 최대값까지 먼저 계산한 다음에 찾아가기
• 리스트를 따로 만들지 말고, 원하는 값이 True인지 False인지 확인하고 계산하기
• 함수는 제일 밖에 선언하기...

import sys
input = sys.stdin.readline
from math import sqrt
tc = int(input())
def main(num):
    a = int(sqrt(num)) + 1
    lst = [True] * (num + 1)  # 소수가 아니면 False로 바꾸기
    lst[0] = False
    lst[1] = False

    for i in range(a + 1):  # num 이하 수 확인

        if lst[i] == True:  # 해당 값이 소수면 (True)
            j = 2
            # 해당 값의 배수를 모두 False로 바꿈
            # num보다 커기면 인덱스 에러 생김
            while (i * j) <= num:
                lst[i * j] = False
                j += 1
    return lst

lst = main(10000)
for _ in range(tc):
    n = int(input())
    for i in range(n//2):
        if lst[n//2 - i]:
            if lst[n-(n//2 - i)]:
                print(n//2 - i, n-(n//2 - i))
                break

• 발전한 흔적...