[Python] 유클리드 호제법 (최대공약수 구하기)

유클리드 호제법 (Euclidean algorithm) 은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나입니다.
최대공약수 (Greatest Common Divisor) : 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미합니다.

공식

만약 i > j 일 경우,
i % j == 0이면 i와 j의 최대공약수는 j이다.
그렇지 않다면, i와 j의 최대 공약수는 j와 i % j의 최대공약수와 같다. (i % j != 0)

예를 들어,

1. 10과 5의 최대공약수: 10%5 = 0 이므로 5가 최대공약수입니다.
2. 10과 8의 최대공약수: 10%8 = 2 이며, 8 % 2 = 0 이므로 2가 최대공약수 입니다.

더 큰 수인 832와 1088의 경우에도

- 1088 % 832 = 256

- 896 % 256 = 64

- 256 % 64 = 0

그러므로 832와 1088의 최대공약수는 64입니다.  

 

Python 코드

n,m의 최대공약수를 구하는 함수입니다.

재귀를 통해 n%m = 0 이 될 때까지 m과 n%m의 최대공약수를 구합니다.