69. 9020(골드바흐의 추측)

import math
T = int(input())
result = ''
# 1 소수값 저장
arr_prime = []
for i in range(0, 10000):
    # 배열은 0부터 시작된다.
    # 인덱스를 값으로 따질거여서 0부터 소수 판별.
    is_prime = True
    for j in range(2, int(math.sqrt(i))+1):
        if(i % j) == 0:
            is_prime = False
            break

    if((not is_prime) or i == 0 or i == 1):
        arr_prime.append(0)
    elif(is_prime):
        # 조건 없이 else로 해도 되지만 확실히 하기위해서 작성
        arr_prime.append(1)

# 2 답 구하기
for _ in range(T):
    n = int(input())
    A = B = int(n/2)  # int로 감싸주지 않으면 실수로 나옴.

    while(True):
        if(arr_prime[A] == 1 and arr_prime[B] == 1):
            result += str(B) + " " + str(A) + "\n"
            break
        A += 1
        B -= 1

print(result)

 

# 문제 요약 : 입력값이 짝수로 들어가고 가장 차이가 적은 소수 두개를 골라서 입력값을 만들어봐~

 

로직은 아래와 같이 돌아갈 것이다.

1. 소수를 리스트에 저장한다.

2. 입력값에서 값 차이가 가장 적은 소수 두개를 고른다.

 

이 문제의 핵심은 값 차이가 가장 적은 소수 두개이다.

 

입력값 내에 소수를 하나하나 비교하여 답을 구할 수 있지만 시간이 오래 걸릴 것 이다.

 

>>[입력값 n을 2로 나눠보자]<<

n/2는 입력값의 중간값이 될 것이고, 하나는 1씩 증가(A) 하나는 1씩 감소(B)로 구하는 것이 시간이 제일 빠르다.

 

424를 만드는 소수는 여러개 있겠지만 위 로직같이 입력값을 중간으로 나누고 상승값과 하락값의 합이 0인 두 소수가 가장 차이가 작다.