9020. 골드바흐의 추측

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

---

풀이

 

import sys
def is_prime(s):
    if s == 1:
        return False
    for i in range(2, int(s**0.5)+1):
        if s % i == 0:
            return False
    return True

#소수조합 경우의 수가 여러 개일 경우, A+B에서 A와 B의 차가 가장 작은 두 요소를 출력해라
#TestCase 개수
n = int(input())

for i in range(n):
    num = int(sys.stdin.readline())
    for j in range(num//2):
        if is_prime(num//2-j) and is_prime(num//2+j):
            a = num//2-j
            b = num//2+j
            print(a, b)
            break

 

설명

 

선행되어야 할 조건은 두 조합에 쓰이는 수에 대한 범위 설정이다.

조합할 두 수는 소수여야 한다.

1) 1인 경우 False

2) 2에서부터 제곱근까지 범위안의 수를 i라고 했을 때

인수를 i로 나눴을 때 몫이 0인 경우 1외에 약수가 또 존재하는 것이니 False

이 두 경우의 수를 제외하면 소수인 것이다.

 

조합이 여러 개일 경우 두 수간의 차가 가장 작은 조합을 출력해야 하는 게 조건이다.

가운데에서부터 1씩 양쪽으로 증감시키는 게 가장 적은 차이를 낸다. 그래서 범위는 그 수 전체를 다 안 보고 반까지만 봐도 된다. 당장 38만 반으로 나눠봐도 19와 19이므로.

 

그런데 양쪽으로 증감시킬 수는 0부터 조건이 만족될 때까지 1씩 차이가 계속 날 수 있으니 이 증감하는 수에 for문으로 루프를 돌려준다.

>> num//2 - j, num//2+j

너무 길어서 안 예뻐보이니 a와 b로 다시 할당하고 출력했다.

그리고 해당 for문에 대해 break로 끝내주어야 처음으로 만족하는 최소한의 차이의 수 조합만 출력하고 끝난다.

break를 안 쓰면 다른 소수 조합을 계속 뱉어낸다.

이 때의 break문은 그 for문 안에서 쓰여야 하고 if문 안에서 j에 조건을 다시 달았으므로 그 조건식 안에서 끝내야 한다.