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

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

문제

풀이

첫번째 풀이 : 시간 초과

n보다 작은 소수를 찾은 뒤 더해서 n이 되고, 둘의 차가 작은 걸 뽑았다..
차이가 작은 소수를 뽑을 때를 좀 더 간단히 해보자.

import sys
input = sys.stdin.readline

# 소수 판별
def is_prime_num(x):
    for i in range(2, int(x**0.5)+1):
        if x%i == 0:
            return False
    return True

t = int(input())
for tt in range(t):

    # n보다 작은 소수 prime_num에 저장
    n = int(input())
    prime_num = []
    for i in range(2, n):
        if is_prime_num(i):
            prime_num.append(i)

    # prime_num에서 i+j=n을 만족시키면서, 차이가 작은 수 출력
    answer = 0
    i_j = []
    for i in prime_num:
        for j in prime_num:
            if i+j == n:
                if i-j <= 0:
                    i_j.append((i,j))

    max_int = 0
    for i,j in i_j:
        max_int = max(i-j, max_int)
        if max_int == max(i-j, max_int):
            a,b = i,j

    print(a,b)

두번째 풀이

에라토스테네스의 체 응용

import sys
input = sys.stdin.readline

# 소수 판별
flg = [False, False] + [True]*10000
for i in range(2,101):
    if flg[i]:
        for j in range(i*2, 10001, i):
            flg[j] = False

t = int(input())
for _ in range(t):
    n = int(input())
    a = n//2
    b = a
    for _ in range(10000):
        if flg[a] and flg[b]:
            print(a,b)
            break
        a -= 1
        b += 1