[백준2609] 최대공약수와 최소공배수

문제

---

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

2609번: 최대공약수와 최소공배수

 

풀이

---

방법 1)

div가 2부터 시작해서 num1과 num2를 모두 나누어 떨어지게 하는 수를 반복적으로 찾아 gcd를 구한다. lcm은 gcd를 이용해 구한다.

 

방법 2)

유클리드 호제법 이용 -> gcd(a,b)=gcd(b,a%b)를 반복적으로 시행해서 a%b가 0이 되는 순간 b가 gcd임을 이용

 

방법 3)

import math를 하여 math.gcd(a,b)를 이용하는 아주 편리한 방법도 있다.

 

코드

---

num1, num2 = input().split()
num1 = int(num1)
num2 = int(num2)
gcd = 1
lcm = 1
div = 2
while True:
    smaller = min(num1, num2)
    if div > smaller:
        break
    if num1 % div == 0 and num2 % div == 0:
        num1 = num1//div
        num2 = num2//div
        gcd *= div
        div = 1
    div += 1
lcm = gcd * num1 * num2
print(gcd)
print(lcm)