백준 2609번. 최대공약수와 최소공배수 (Python / 파이썬)

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

문제 풀이

어떤 두 수의 최대공약수는

두 수 중 큰 수에서 작은 수로 나눈 나머지를

두 수 중 작은 수에서 계속 나누어주어 구할 수 있습니다.

 

어떤 두 수의 최소공배수는

두 수의 곱을 최대공약수로 나눈 몫으로

구할 수 있습니다.

따라서 최대공약수와 최소공배수를 구하는

함수를 각각 만들어 구해주었습니다.

 

1. 최대공약수를 구하는 함수는 b가 0보다 클 때까지만

a는 b로, b는 a를 b로 나눈 나머지로 

갱신시켜주고 b가 0이되면 a를 반환하도록 해주었습니다.

 

2. 최소공배수를 구하는 함수는

a와 b를 곱한 값을 최대공약수로 나눈 몫을 반환하도록 해주었습니다.

---

My Code

# 최대공약수 구하기
def gcd(a, b):
    while b > 0: # b가 0이되면 종료
        a, b = b, a % b # a를 b로 나눈 나머지를 계속해서 나눠 줌
    
    return a # b가 0이 되면 a를 반환

# 최소공배수 구하기
def lcd(a, b):
    return (a * b) // gcd(a, b) # 두 수의 곱을 최대공약수로 나눈 몫을 반환

a, b = map(int,input().split()) # 두 수
print(gcd(a, b)) # 최대공약수 출력
print(lcd(a, b)) # 최소공배수 출력