gcd_lcm.py

"""
- Greatest Common Divisor(최대공약수) by Euclidean algorithm(유클리드 호제법)
> Reference: Wiki(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)

- Least Common Multiple(최소공배수): 두 수의 곱 / 최대공약수
"""


__all__ = ['gcd_while', 'gcd_recursive', 'lcm']


def gcd_while(a: int, b: int) -> int:
    """
    Args:
        a (int)
        b (int)
        
    Returns:
        int
    """
    while b != 0:
        a, b = b, a % b
    return a


def gcd_recursive(a: int, b: int) -> int:
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a: int, b: int) -> int:
    """
    Args:
        a (int)
        b (int)
    
    Returns:
        int
    """
    return (a * b) // gcd_while(a, b)