<백준 문제풀이: 9020번> 파이썬 - 골드바흐의 추측

1주일전에 풀었다가 못 풀어서 오늘 다시 풀어본 문제이다:

시간초과가 뜬 풀이:

import sys

T = int(sys.stdin.readline())

all_num = [int(x) for x in range(2, 10001)]
prime_list = []

def is_Prime(n):
    if n == 1:
        return False
    else:
        for i in range(2, int(n**0.5)+1):
            if n%i == 0:
                return False
        else:
            return True

for j in all_num:
    if is_Prime(j):
        prime_list.append(j)

for k in range(T):
    N = int(sys.stdin.readline())
    small_prime = []
    for ii in prime_list:
        if ii < N:
            small_prime.append(ii)
    possible_list = []
    for jj in small_prime:
        for kk in small_prime:
            if jj+kk == N:
                possible_list.append([jj, kk])
    if len(possible_list) == 2:
        print("%d %d" %(possible_list[0][0], possible_list[0][1]))
    else:
        difference_list = []
        for iii in possible_list:
            difference_list.append([abs(iii[0]-iii[1]), iii])
        print("%d %d" %(min(difference_list)[1][0], min(difference_list)[1][1]))

처음 풀었던 방식은 이것이다. 하지만 너무나도 복잡하고, 시간초과도 뜰뿐더러, 알아보기도 힘들다. 다른 방식이 필요했다.(위의 방식에 대해서는 설명하지 않겠다. 어차피 시간초과가 뜬 방식이다.)

제출한 정답

import sys

T = int(sys.stdin.readline())

prime_set = set(range(2, 10001))
for i in range(2, 10001):
    for j in range(2, int(i**(1/2))+1):
        if i%j == 0:
            prime_set -= set(range(j*2, 10001, j))

def is_prime(n):
    if n in prime_set:
        return True
    else:
        return False

for i in range(T):
    n = int(sys.stdin.readline())
    half_num = n//2
    count = 0
    for i in range(n//2):
        small_prime = half_num-count
        big_prime = half_num+count
        if is_prime(small_prime) and is_prime(big_prime):
            print("%d %d" %(small_prime, big_prime))
            break
        else:
            count += 1

곰곰히 생각해보니 첫번째 방법처럼 복잡하게 할 필요가 없다. 어차피 주어지는 n 값은 10001까지의 값이기 때문에, 이 범위 안의 소수들을 구해서 prime_set에 정의해주고, 이 prime_set에 존재하는지 존재하지 않는지 확인해주는 is_prime() 함수를 정의해준다. 마지막으로 주어지는 n값에 대하여 n은 짝수이므로 n의 절반 값에서 시작해준다. n의 절반 값에서 count만큼 빼고 더한 값을 서로 더해주고, 이 값이 소수인지 확인만 해주면 된다.