[python] 최소공배수, 최대공약수, 유클리드 호제법

유클리드 호제법을 사용한 최소공배수 구하기가 정석이지만! (아래코드 참고)

def gcd(m, n):  #최소공배수
    if n == 0:
        return m
    elif m % n == 0:
        return n
    return gcd(n, m%n)

def lcm(m, n):  #최대공약수
    return (m * n) // gcd(n, m)

파이썬에서는 라이브러리로 쉽게 해결 가능하다. (파이썬 3.9이상만 lcm 지원)

import math
print(math.gcd(78696, 19332)) # 36, 최소공배수
print(math.lcm(33,66)) # 66, 최대공약수