[Baekjoon/Python] 2609번: 최대공약수와 최소공배수 - 효과는 굉장했다!

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

알고리즘 분류

• 수학
• 정수론
• 유클리드 호제법

 

SOLUTION

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

def gcd(x,y): # 최대공약수(유클리드 호재법)
    mod = x % y 
    while mod > 0:
        x = y
        y = mod
        mod = x % y
    return y    
    
def lcm(x, y): # 최소공배수
    return x * y // gcd(x,y) # 두 수를 곱하고 최대공약수로 나눈 값 == 최소공배수

print(gcd(a, b))
print(lcm(a, b))

 

※ 유클리드 호재법이란?

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95