Python 재귀함수로 GCD 최대공약수 구하기

 

 

 

 

GCD(Greatest Common Divisor)를 구하는 대표적인 알고리즘으로 유클리드 호제법이 있다.

유클리드 호제법

 - 두 자연수 A, B 에 대햐여 A > B 일 때 A를 B로 나눈 나머지를 R이라고 하자

   이 때 A와 B의 최대공약수는 B와 R 의 최대공약수와 같다.

 

ex) GCD(192, 162) = 6

def GCD(a, b):
    if a % b == 0:
        return b
    return GCD(b, a%b)

print(GCD(192, 162))

6

 

 

 

출처

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3