9020번: 골드바흐의 추측

9020번: 골드바흐의 추측

 

에라토스테네스의 체를 활용해서 풀면 되는 문제다.

특정 짝수를 만드는 두 소수 중에서 두 소수 사이의 차가 적은 친구들이 답이다.

temp 변수를 선언해서 최솟값이 for문을 돌때마다 초기화되도록 로직을 작성했다.

 

import math

check = [True] * 10001
check[1] = False

def erathos(n):
    for i in range(2, int(math.sqrt(n))+ 1):
        if check[i]:
            j = 2
            while i * j <= n:
                check[i*j] = False
                j += 1


t = int(input())
arr= []
for i in range(t):
    num = int(input())
    arr.append(num)

erathos(max(arr))


for num in arr:
    temp = 10000
    for i in range(num):
        if check[i] and check[num-i]:
            if temp > num - 2 * i and num >= 2 * i:
                a, b = i, num-i
    print(a, b)