[백준] 2609번: 최대공약수와 최소공배수 (Python)

[2609번] 최대공약수와 최소공배수

문제

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

입력

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

출력

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

---

풀이 1) 유클리드 호제법 활용

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 의미한다.

2개의 자연수 $a, b$ (단, $a$>$b$)에 대해 $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $a$와 $b$의 최대공약수는 $b$와 $r$의 최대공약수와 같다. $b$를 $r$로 나눈 나머지 $r'$를 구하고, 다시 $r$을 $r'$로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 $a$와 $b$의 최대공약수이다.

즉, 위의 과정을 계속해서 반복하여 나머지가 0이 될 때까지 나누어 나오는 수가 최대공약수이다.

2개의 자연수 $a, b$의 최소공배수는 $a$와 $b$의 곱을 $a$와 $b$의 최대공약수로 나눈 것과 같다.

def gcd(a, b):
	while b > 0:
    	a, b = b, a % b
    return a

def lcm(a, b):
	return (a * b) // gcd(a, b)
    
print(gcd(a, b))
print(lcm(a, b))

풀이 2) 내장함수 활용

파이썬 모듈 중 math에 최대공약수와 최소공배수를 구하는 함수가 내장되어 있어 아래와 같이 간단하게 풀 수 있다. (처음에는 풀이 1로 어떤 방식으로 작동하는지 파악하는 것이 중요!)

import math

a, b = map(int, input().split())

print(math.gcd(a, b))
print(math.lcm(a, b))