[백준/수학] 2609 최대공약수와 최소공배수(Python, 파이썬)

www.acmicpc.net/problem/2609  

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

 

 

최대공약수(GCD): 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.

최소공배수(LCM): 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.

 

최대공약수는 유클리드 호제법을 이용하여 구한다.

- a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r) 이다.

- r이 0이면 그 때 b가 최대 공약수이다.

 

최소공배수는 GCD를 응요해서 구할 수 있다. 

- 두 수 a, b의 최대공약수 g라고 했을 때 $l = g\times (a/g)\times (b/g)$이다.

 

 

# 최대공약수
def gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

# 최소공배수
def lcm(a, b):
    return int(a*b/gcd(a,b))

a, b = map(int, input().split())
print(gcd(a, b))
print(lcm(a,b))