유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘
소인수 분해를 이용한 공통된 소수들의 곱으로도 표현할 수 있지만 더 간단한 방법을 제시함

핵심이론

1. 큰 수를 작은 수로 나누는 MOD 연산을 수행(%)
2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행
3. 2단계를 반복하다가 나머지가 0이 되는 순간의 작은 수가 최대 공약수
   

코드구현

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

num1 = 48
num2 = 18

gcd = euclidean_gcd(num1, num2)