유클리드 호제법(최소공배수, 최대공약수 구하기) - 파이썬(python)

유클리드 호제법을 이용해서 최대공약수 구해본다

파이썬코드

x와 y의 최대공약수 구하는 함수. 이 함수를 이용해서 최소공배수도 간단하게 구할 수 있다.

# 최대공약수
def gcd(x,y):
    
    while y:
        x,y=y,x%y
    return x

# 최소공배수
def lcm(x,y):
    res=(x*y)//gcd(x,y)
    return res