파이썬에서 최대 공약수 구하기 (유클리드 호제법)

유클리드 호제법

1. 두 수 $a$와 $b$가 있을 때, $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $GCD(a, b) = GCD(b, r)$입니다.
2. 이 과정을 반복하여 나머지가 0이 될 때의 $b$가 최대 공약수입니다.

재귀함수로 유클리드 호제법 구현

function gcd(a,b):
    if a%b == 0:
        return b
    else:
        gcd(b, a%b)

반복문으로 유클리드 호제법 구현

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

다음과 같은 방법으로 구현할 수 있습니다.

혹시 까먹을 거 같아서 작성했습니다.~ ㅎ