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

문제

나의 답안

import sys
input=sys.stdin.readline

t=int(input())
arr=[]
def prime(n):#소수 판별
    for j in range(2,int(n**0.5)+1):
        if n%j==0: #약수가 존재하므로 소수가 아님
            break   #더이상 검사할 필요가 없으므로 멈춤
    else:
        return True
            
for _ in range(t):
    n=int(input())
    a=n//2
    b=a
    while True:
        if prime(a)==True and prime(b)==True:
            print(a,b)
            break
        else:
            a-=1
            b+=1

접근 방법

• 문제의 조건에서 두 소수의 차이가 가장 작은 것부터 출력한다고 하였으므로 n의 절반(n//2)부터 쁠마1씩 차를 줄여나가면서 구해주면 된다.
• 에라토스테네스의 체(소수 구하기)를 사용하여 소수를 구할 때의 시간 복잡도를 줄여준다.