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

코드

유클리드 호제법으로 최대공약수를 구하면 최소공배수는 쉽게 구할 수 있다.

2021.03.14 - [Algorithm & Data structure] - [알고리즘] 유클리드 호제법 (최대공약수, 최소공배수)

[알고리즘] 유클리드 호제법 (최대공약수, 최소공배수)

# 유클리드 호제로 최대 공약수 구하기

# 유클리드 호제법
# 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다.
# 이때 A와 B의 최대공약수는 B와 R의 최대 공약수와 같다

# 최소공배수 = 두 수의 곱 / 최대공약수

def gcd(a,b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

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

print(gcd)
print(a * b // gcd)