#151 백준 파이썬 [9020] 골드바흐의 추측

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

 

#Solution

다음과 같은 알고리즘으로 효율적으로 구하였다.

1) 10000 이하의 모든 소수 생성

2) 두 소수의 값을 더했을 때 짝수이며, 10000 이하인 모든 소수를 goldbach 리스트 안에 넣어줌

3) 리스트 안의 숫자 페어 중 곱이 가장 큰 수 = 가장 인접한 수를 출력

# 재료가 될 소수 생성
prime_ox = [True for _ in range(10001)]

for i in range(2, int((10001) ** 0.5)):
    if prime_ox[i] == True:
        for j in range(i+i, 10001, i):
            prime_ox[j] = False 

prime_list = [i for i, j in enumerate(prime_ox) if j == True and i >=2 ]

#구한 소수를 더하여 골드바흐 리스트 안에 넣어주기 (여러개 가능)
goldbach = [[] for _ in range(10001)]

for i in range(len(prime_list)):
    for j in range(i, len(prime_list)):
        even_num = prime_list[i] + prime_list[j]
        if even_num % 2 == 0 and even_num <= 10000:
            goldbach[even_num].append([prime_list[i], prime_list[j]])

case = int(input())

for _ in range(case):
    num = int(input())
    answer = [0, 0]
    
    # 곱이 가장 큰 수: 가장 근접한 수
    for [i, j] in goldbach[num]:
        if i * j > answer[0] * answer[1]:
            answer[0] = i
            answer[1] = j
    
    print("%s %s" % (answer[0], answer[1]))