[백준] 9029번 - 골드바흐의 추측

1. 문제

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

 

 

2. 코드

import math

sosu = []

for i in range(2, 10000):
    flag = 0
    temp = int(math.sqrt(i))
    for j in range(2, temp+1):
        if i%j == 0:
            flag = 1
    if flag == 0:
        sosu.append(i)

n = int(input())
for i in range(n):
    num = int(input())
    for j in range(num//2, 1, -1):
        if (j in sosu) and (num-j in sosu):    
            print(j, num-j)
            break

 

 

 

3. 알고리즘

1) 1~10000까지 모든 소수를 sosu라는 리스트에 저장

2) 숫자가 입력되면 num//2까지 돌면서 j와 num-j가 모두 소수 리스트에 있는지 확인.  이 때, 두 수의 간격이 좁은 것부터 구하기 위해 num//2부터 거꾸로 내려간다. 둘다 소수 리스트에 있으면 j + (num-j) = num 이ㅣ고, j와 num-j 모두 소수이므로 조건 만족.

3) 끝