본문 바로가기

알고리즘/백준알고리즘

[백준 알고리즘/Python3] 9020 골드바흐의 추측

문제이해

처음에 생각했던건

 

  • 들어온 n값에 대해 소수를 구한다.
  • 가장 작은 소수를 뺀다.
  • 그 뺀값이 구한 소수들로 합쳐진 값이 나온다면 그것이 골드바흐 파티션이다.
  • 나오지 않는다면 다음 소수 리스트로 넘어간다.

이렇게 했더니 시간초과가 나옵니다.

다른방법을 써야할 거 같습니다.

 

코드

#소수를 구하는 함수
def prime_num(n):
    a = [False, False] + [True] * (n-1)
    b = []

    #에라토스테네스의 체로 리스트a를 조정한다.
    for i in range(2, n+1):
        if(a[i]):
            for j in range(i*2, n +1, i):
                a[j] = False

    #리스트a가 True일 때 인덱스를 출력
    for i in range(n+1):  
        #소수이면
        if(a[i]):
            b.append(i)


    #소수 판별
    for j in b[::-1]:
        num = n - j                #첫 번째 소수를 뺀다.
        if(num>1 and a[num]):      #1이상 소수들만
            for k in b:            
                if((j + k) == n):  #같은 값 중에서
                    if(j <= k):    #두 소수의 차이가 가장 적은 것
                        print(j, k)
                        return

       

#나머지를 소수 리스트로 돌려서 합친 값이 나오면 그것이 골드바흐 파티션
#나오지 않는다면 다음 소수 리스트로 넘어간다.

case = int(input())
while(case > 0):
    test_case = int(input())

    prime_num(test_case)
    case -= 1

 

다른 방식을 생각 해보니

입력받은 값을 2로 나누고 

몫부터 소수를 구하면 되지 않을까? 생각했습니다.

 

    for i in range(n//2,n+1):  
        #소수라면
        if(a[i]):
            if(a[n - i]):
                print(n-i, i)
                return

원래 소수를 구하고 리스트로 만들었던 로직이였습니다.

 

여기서 주어진값(n)을 2로 나눈 몫(n//2)부터 주어진 값(n)까지 실행하면 

중간에서 가장 가까운 값이 "두 소수의 차이가 가장 작은 것" 이 되니 

주어진 값(n) 에서 소수를 뺀 값이 주어진 값(n)이라 생각하지말고 그냥 소수라면? 이라는 생각이 더 문제에 맞다고 생각했습니다.

 

그래서 n-소수, 소수 를 출력하고 가장 가까운 값이 출력이 되었으니 함수는 종료되야 합니다.

 

다시 생각한 코드

#소수를 구하는 함수
def prime_num(n):
    a = [False, False] + [True] * (n-1)
    b = []

    #에라토스테네스의 체로 리스트a를 조정한다.
    for i in range(2, n+1):
        if(a[i]):
            for j in range(i*2, n +1, i):
                a[j] = False

    
    for i in range(n//2,n+1):  
        #소수라면
        if(a[i]):
            if(a[n - i]):
                print(n-i, i)
                return

#입력받은 만큼만 while문 돈다.
case = int(input())
while(case > 0):
    test_case = int(input())

    prime_num(test_case)
    case -= 1

 

728x90