[백준] 기본 수학 2 - 9020번 (Python)

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

9020번: 골드바흐의 추측

---

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

코드 정답

def sosu(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

for _ in range(int(input())):
    num = int(input()) # 주어지는 짝수

    a, b = num//2, num//2
    while a > 0:
        if sosu(a) and sosu(b):
            print(a, b)
            break
        else:
            a -= 1
            b += 1

풀이

• 1행 : def sosu(n) 즉, sosu(i)의 값을 가져와 num으로 변형 후 2~8행을 실행한다.
• 2~3행 : n에 저장된 값이 1이라면 False를 리턴한다.
• 4행 : 2부터 n에 저장된 값을 제곱근 시킨 값까지를 i에 선언한다.  제곱근까지의 약수를 구하면 해당 약수를 포함하는 수를 모두 제거할 수 있다고 한다. ex) i = 12에서 12의 약수는 1 2 3 4 6 12가 된다. int(sqrt(12)) = 3이고 12는 3으로 나누어 떨어지므로 더 검사할 필요가 없다고 한다.
• 5~6행 : n을 i로 나눈 값의 나머지가 0일 경우 false를 리턴하여 값을 돌려주지 않는다.
• 7행 : 5~6의 값에 충족하지 않아 리턴이 되지 않을 경우 작동된다. True를 반환하여 num에 저장된 값을 반환한다.
• 9행 : 정수를 입력받고 입력받은 정수만큼 10~19행을 반복한다.
• 10행 : 정수를 입력받고 변수 num에 저장한다.
• 12행 : num을 2로 나눈 값 중 정수를 각각 a와 b에 저장한다.(어차피 짝수만 입력되기에 소숫점이 나올 일은 없다.)
• 13행 : a가 0보다 클 경우 14~19행을 반복한다.
• 14행 : 변수 a와 b에 저장된 값이 sosu()함수에 들어가 둘 다 True를 반환하게 된다면 15~16행을, 아니라면 18~19행을 반복한다.
• 15~16행 : a와 b에 저장된 값을 출력 후 중단하고 for문으로 되돌아간다.
• 18~19행 : a에 저장된 값에 1을 빼주고, b에 저장된 값이 1을 더해준 후 for문으로 되돌아간다.