[Python] 유클리드 호제법(재귀로풀기)

유클리드 호제법이란?

두 자연수에 대한 최대공약수를 구하는 알고리즘

두 자연수 A, B(A>B)에 대하여 A를 B로 나눈 나머지를 R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

 

# 유클리드 호제법
# 꼭 a > b가 아니어도 됨
def GCD(a, b):
    if a % b == 0: # a와 b가 배수관계라면
        return b
    else:
        return GCD(b, a%b)

print(GCD(280, 100)) # 20
print(GCD(100, 280)) # 20