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

출처 : www.acmicpc.net/problem/2609

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

최소공배수를 구할 때, 유클리드 호제법을 이용하였다. 이 문제는 유클리드 호제법을 공부하기 위해 푼 문제이기도 하다. 유클리드 호제법은 r = a%b라 할 때, gcd(a,b) = gcd(b,r)이 같고 이를 r이 0일 때 까지 반복하면 그 때, b 값이 최대공약수이다. 최소공배수는 최대공약수와 a랑 b를 각각 최대공약수로 나눈 값들을 모두 곱하면 구할 수 있다.

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
 
a,b = map(int,input().split())
 
Gcd = gcd(a,b)
Lcm = Gcd*(a//Gcd)*(b//Gcd)
print(Gcd)
print(Lcm)