Python으로 알고리즘 공부 08. 최대공약수, 최소공배수 알고리즘

최대공약수, 최소공배수 알고리즘

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

• 최대공약수를 구하는 함수를 ​라고 하자.

• ​ 이라면, ​ 임이 성립.

• ​ 이 이라면, ​ 임이 성립한다.

def gcd(a, b):
    mod = a%b
    while mod > 0:
        a = b
        b = mod
        mod = a%b
    return b

최소공배수

• 최소공배수는 a과 b의 곱에 최대공약수를 나누어 준 것과 같다.

def lcm(a, b):
    return a*b//gcd(a,b)

• 최대공약수 (GCD : Greatest Common Divisor)

• 최소공배수 (LCM : Least Common Multiple)