[Algorithm]유클리드 호제법 - 두 수의 최대공약수를 구하기

유클리드 호제법이 뭘까? 

두 수의 최대공약수를 구하는 알고리즘이다. 

💡 호제법 : 두 수가 서로 상대 수를 나눠서 원하는 수를 얻는 알고리즘 

 

두 양의 정수 a, b (a>b)에 대해서 r = a % b (r은 a를 b로 나눈 나머지) 이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
반복적으로, rr = b % r 이라고 하면, rr, rrr, ...이 0이 될 때까지 이 과정을 반복한다. 
rr이 0이면 a, b의 최대 공약수는 r이 된다. 

 

유클리드 호제법을 예시를 통해서 보자! 

📌 2058과 1071의 최대공약수 구하기 

먼저, 큰 수(2058)를 작은 수(1071)로 나눈다. 

2058 % 1071 = 987

나머지(987)가 0이 아니기 때문에, 1071을 987로 나누고 이 과정을 나머지가 0이 될 때까지 반복한다. 

1071 % 987 = 84 
987 % 84 = 63 
84 % 63 = 21 
63 % 21 = 0

이때, 63 % 21 = 0이라는 것은, 최대공약수가 21이라는 말이다. 

 

유클리드 호제법으로 구현하기

# python
def Euclidean(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

 

 

참고 
https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95
https://tech.lonpeach.com/2017/11/12/Euclidean-algorithm/