[파이썬 백준] 2609번 최대공약수와 최소공배수

❓ 문제

---

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

>  입력

---

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

>  출력

---

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

✔️ 풀이

---

# 유클리드 호제법
def ys(x, y):
    if y:
        return ys(y, x % y)
    else:
        return x

a, b = map(int, input().split())
print(ys(a, b))
# 최대 공약수 * 최대 공배수 = a * b
print(int(a * b / ys(a, b)))

유클리드 호제법을 이용해 최대 공약수를 구하고,

(최대 공약수) * (최대 공배수) = a * b인 점을 이용하여 최대 공배수를 구해주었다.

알아보니 파이썬에 최대 공약수와 최대 공배수를 구하는 함수가 있었다.

import math
math.gcd(숫자) # 최대 공약수
math.lcd(숫자) # 최소 공배수

💬 평가

---

Notice: 이 게시물은 백준 사이트를 참고하였습니다.