[백준/Python] 9020번 골드바흐의 추측 (기본수학2)

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의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

 

 

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

9020번: 골드바흐의 추측

 

---

 

풀이 코드

 

def sosu(x):

    if x == 1:
        return False

    for j in range(2, int(x**0.5) +1):
        if x % j == 0:
            return False

    return True


t = int(input())

for _ in range(t):
    num = int(input())

    for a in range(num//2, 0, -1):
        if sosu(a) and sosu(num-a):
            print(a, num-a)
            break

 

 

def sosu(x):

 

 

- 소수임을 판별하기 위한 함수 sosu 작성

 

- x 값을 파라미터로 받음

 

 

 

if x == 1:    /    return False

 

 

- 파라미터 값 x 가 1인 경우

 

- 1은 소수에 해당하지 않음

 

- False 값을 리턴

 

 

 

for j in range(2, int(x ** 0.5) +1):

 

 

- (수) ** 0.5 를 통해 특정 수의 제곱근을 구할 수 있음

 

- x 의 제곱근까지 나누어 떨어지는 수가 있는지 판별

 

- range() 를 사용하여 2부터 x^0.5 까지 for 문을 반복

 

- i 값으로 2 부터 x^0.5 까지 들어감

 

- 1보다 큰 자연수로 나누어야 하므로, 2부터 시작

 

 

 

if x % j == 0:    /    return False

 

 

- x 를 j 로 나누었을 때, 나누어 떨어지는 경우 소수가 아님

 

- False 값을 리턴

 

 

 

return True

 

 

- 앞서 x 가 1인 경우와, 약수가 있는 경우가 아니면, 소수임

 

- True 값을 리턴

 

 

 

t = int(input())

 

 

- 테스트 케이스의 개수를, 변수 t 에 저장

 

- input() 을 통해 한 줄의 문자열을 입력받음

 

- 입력받은 문자열을 정수로 처리하기 위해 int() 함수를 사용

 

 

 

for _ in range(t):

 

 

- range() 를 사용하여, 테스트 케이스의 개수 t 만큼 for 문을 반복

 

 

 

num = int(input())

 

 

- 각각이 테스트가 한 줄 씩 주어지므로, for 문 안에 input() 작성

 

- 입력받는 짝수를, 변수 num 에 저장

 

- 입력받은 문자열을 정수로 처리하기 위해 int() 함수를 사용

 

 

 

for a in range(num//2, 0, -1)

 

 

- 두 소수의 차이가 가장 작은 것을 출력해야 하므로, 가능한 소수 쌍 중 가운데 값을 범위로 잡음

 

- 가운데 값인 (입력값 // 2) 부터 1까지 for 문을 반복

 

 

 

if sosu(a) and sosu(num-a):

 

 

- a 와 num-a 값을 sosu 함수에 넣어, 소수인지 판별

 

- a 와 num-a 값이 모두 소수인 경우

 

 

 

print(a, num-a)

 

 

- 소수에 해당하므로, a 와 num-a 값을 출력

 

 

break

 

 

- 소수 쌍을 출력하였으므로, break 문으로 for문을 빠져나옴

 

 

 

 

 

 

 

나동빈 '이것이 코딩 테스트다 with 파이썬' 책을 참고하여 작성하였습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC,