[파이썬] 백준 연습문제 #9020. 골드바흐의 추측 완벽해설

문제

 

 

해설

 

이 문제를 풀기 위한 로직은 어떠한 숫자가 주어졌을 때, 그 숫자의 절반값을 기준으로 오른쪽값 왼쪽값을 탐색해나가며, 만약 오른쪽값과 왼쪽값 모두 소수이고, 두 숫자의 합이 주어진 숫자와 같을 경우 출력해주도록 코드를 작성해주면 된다.

 

그리고 더 나아가 탐색에 대한 코드도 더욱 구체적으로 작성을 해주어야 하는데, 이 경우는

 

1. 만약 오른쪽 왼쪽의 수가 모두 소수인데, 이 둘의 합이 주어진 수보다 작을 경우

   -> 오른쪽에 있는 값에 +1을 해주는 방식으로 탐색

2. 만약 오른쪽 왼쪽의 수가 모두 소수인데, 이 둘의 합이 주어진 수보다 클 경우

  -> 왼쪽에 있는 값에 -1을 해주는 방식으로 탐색,

3. 만약 오른쪽은 소수이고 왼쪽은 소수가 아닐 경우

  -> 왼쪽에 있는 값에 -1을 해주는 방식으로 탐색

4. 만약 왼쪽이 소수이고 오른쪽은 소수가 아닐 경우

  -> 오른쪽에 있는 값에 +1을 해주는 방식으로 탐색,

5. 만약 둘다 소수가 아닐 경우

  -> 왼쪽은 -1, 오른쪽은 +1을 해주는 방식으로 탐색

 

위와 같은 로직으로 탐색코드를 작성해주면 된다. 살짝 복잡해 보이긴 하지만, 실제로 직접 펜으로 적어가며 시뮬레이션을 해보면 위의 로직으로 진행해야 함을 알 수 있다.

 

따라서 결과적으로

1. 오른쪽 왼쪽 다 소수이고, 합이 주어진 수와 같을 경우 출력을 하고 마치는 코드.

2. 그렇지 않을 경우 탐색 코드

이 두가지 코드를 while 문으로 작성을 해주면 된다.

 

 

코드

 

import sys
import math

T = int(input())
nums = []

def isPrime(number):
    for i in range(2, int(math.sqrt(number))+1):
        if (number%i == 0):
            return False        
    return True

# for i in range(10, 1-1, -1):
#     print(i)

for _ in range(T):
    nums.append(int(input()))
    
for num in nums:
    middle_l = num//2
    middle_r = num//2
    while (True):
        if (isPrime(middle_l) and isPrime(middle_r)):
            if (middle_l + middle_r == num):
                print(middle_l, middle_r)
                break
            else:
                if (middle_l + middle_r < num):
                    middle_r += 1
                else:
                    middle_l -= 1
            # else:
        elif (isPrime(middle_l) and not isPrime(middle_r)):
            middle_r += 1
        elif (not isPrime(middle_l) and isPrime(middle_r)):
            middle_l -= 1
        else:
            middle_l -= 1
            middle_r += 1

 

 

결과