백준 9020번 골드바흐의 추측

1. 문제

2. 나의 풀이

• 시간초과 나는 나의 풀이

import sys
import heapq

count = int(input())


def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


def find_primes(n):
    primes = []
    for i in range(2, n):
        if is_prime(i):
            primes.append(i)
    return primes


for _ in range(count):
    num = int(input())
    # print(num)
    primes = find_primes(num)
    h = []
    for p in primes:
        for r in primes:
            if p+r == num:
                heapq.heappush(h, (abs(p-r), p, r))
    a, b, c = heapq.heappop(h)
    print(b, c)

3. 남의 풀이

• https://leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-9020%EB%B2%88-%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98-%EC%B6%94%EC%B8%A1-in-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%89%BC%EA%B2%8C-%ED%92%80%EC%96%B4%EB%B3%B4%EA%B8%B0

# n이하의 숫자들 중 소수 찾기
def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]
 
# n이하의 소수들 중 합이 n
def sosu(n):
    li=prime_list(n)
    idx = max([i for i in range(len(li)) if li[i]<=n/2])
    for i in range(idx,-1,-1):
        for j in range(i,len(li)):
            if li[i]+li[j]==n:
                return [li[i],li[j]]
 
for _ in range(int(input())):
    n=int(input())
    print(" ".join(map(str,sosu(n))))

4. 느낀 점