백준[9020번]:: 골드바흐의 추측(Python,파이썬)

www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

 

 

처음 쓴 코드:

 

import math

def IsPrime(num):
    a = int(math.sqrt(num))
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0: 
                return False
        return True

Num_list = list(range(2,246912))
Sort_list = []
for i in Num_list:
    if IsPrime(i):
         Sort_list.append(i)

T = int(input())
for i in range(T):
    N = int(input())
    oup = []    
    for j in Sort_list:
        if N >= j:
           oup.append(j) 
    print(oup)

    for i in oup:
        for j in oup:
            if N == i+j:
                print("{0} + {1} = {2}".format(i,j,i+j))
    print(oup)   

 

위 문제는 입력한 N값의 소수중에 작은것부터 두수의 차이가 작은 것을 출력하는 문제이다.

현재 해결하지 못했지만, 일단 먼저 에라토스테네스의 체를 이용하여 먼저 소수의 리스트를 만든 후, 이 리스트 중 에서 합이 입력한 값이랑 맞을때, 그때의 두 수를 비교하면 출력하면 무언가 될 것 같았다. 하지만 아직 두 수를 비교하는 코드도 완성하지 못하였고, 시간복잡도도 매우 낮기때문에 시간초과가 걸릴 것이다. 빨리 생각하여 수정해야 할 것 같다.