최대공약수(GCD) 구하기 - 유클리드 호제법

유클리드 호제법 (연제법, Euclidean algorithm)
A = Bq + R
G(A, B) = G(B, R)
A와 B의 최대공약수와 B와 R의 최대공약수가 같다.

두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (단, a > b)

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

>> 이를 이용해서 a를 b로 나눈 나머지 r를 구하고, 다시 b를 r로 나눈 나머지를 구하는 과정을

  나머지 r이 0이 될 때까지 반복하면 마지막의 b가 a와 b의 최대공약수가 된다. 

 

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

print(gcd(a, b))