success - Baekjoon 9단계-6 9020번 골드바흐 추측 python3

문제

 

문제의 마지막에 두 소수의 차이가 가장 작은 것을 출력한다고 했으니까

일단 입력이 짝수이기 때문에 2로 나눌 수 있고

거기서 나눠진 x,y 를 계속 소수인지 판별해서

1씩 증감해 나가는 방법을 선택했다

 

원트원클

https://github.com/cyanindy/baekjoon_online_judge/blob/main/python3/step9/9020.py

GitHub - cyanindy/baekjoon_online_judge: https://www.acmicpc.net/

 

코드이다

 

시간이 조금 오래걸렸는데

 

소수는 2를 제외하면 모두 홀수이기때문에

2씩 증감해 나가면서 비교해보려고 했지만

그러면 초반에 입력이 4인경우, 6인경우, 8인경우만 정의해주면 이후 큰 수에 대해서는 훨씬 빠르게 돌아갈것 같아서

더 고민해보았다

 

#https://www.acmicpc.net/problem/9020

def pn(ad) :
    for i in range(2,ad) :
        if i*i<= ad :
            if ad%i==0 : return False
    return True
            
def GB_conjecture(idx) :
    #if idx==8 : return 3,5
    x,y=int(idx/2), int(idx/2)
    while True : 
        _x=pn(x)
        _y=pn(y)
        if _x and _y :
            return x,y
        else :
            x-=2
            y+=2

    

n=int(input())
for run in range(n) :
    num=int(input())
    a,b= GB_conjecture(num)
    print(a,b)

 

ㅋㅋㅋㅋ 돌려보니까

 

8일때 무한루프

12일때 무한루프

16일때 무한루프 ㅋㅋㅋㅋ

 

걍 1씩 비교하는게 맞았나 싶다 ㅋㅋ

시간을 더 줄일 수는 있을거같은데

그건 나중에~