초이의 끄적끄적

단계별풀기 - 기본수학2

# 9020 골드바흐의 추측 (실버1)

• 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.
• 각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
• 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기 
  • prime 값이 True면 소수
• point. 두 소수의 차이가 가장 작은것을 출력한다 & 작은 소수부터 출력한다 -> 중간값부터 확인해본다
  • n = 8 이면 4,4 -> 3,5(break) -> 2,6 -> 1,7 순으로 확인
  • n = 10 이면 5,5(break) -> 4,6 -> 3,7 -> 2,8 -> 1,9 순으로 확인한다. 
  • n = 16  이면 8,8, -> 7,9 -> 6,10 -> 5,11(break) -> ...

def isprime(n):
    n += 1
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False
    return prime

for _ in range(int(input())):
    n = int(input())
    prime_list = isprime(n)
    half = n//2
    for i in range(half, 1, -1):
        if prime_list[i] and prime_list[n-i]:
            print(i, n-i)
            break