유클리드 호제법 - 최대공약수, 최소공배수

두 수 n, m 의 최대 공약수를 구하는 방법으로, 단순하게 반복문을 통해 구할수도 있다. 

하지만 효율적인 방법은 유클리드 호제법을 이용하는 것이다.

 

유클리드 호제법

두 수 n 과 m의 최대공약수는 m 과 n%m(n에서 m을 나눈 나머지) 의 최대공약수와 같다.

➡️ n 과 m의 최대공약수 == m과 n%m의 최대공약수

그림과 같이 n 자리에 m을 대입하고, m 자리에 n%m을 대입해서 나머지를 구하다 보면,

결국에는 나머지가 0이 되는 순간이 오고, 그 때의 m이 두 숫자의 최대 공약수가 된다. 

def solution(n, m):
    while m > 0: #1
    	n, m = m, n%m #2
    return n #3

1. m이 0보다 클때까지 반복한다.

2. n 자리에 이전 m을 대입하고, m자리에 n % m을 대입한다. 

3. m이 0이 된 순간의 n이 이전에 n % m == 0 일때의 m 이므로 n이 최대공약수이다. n을 반환한다. 

 

최소공배수 구하기

두 수 n과 m의 최소공배수는 n과 m의 최대공약수를 알면 쉽게 구할 수 있다. 

n과 m의 곱을 최대공약수로 나눈 몫이 최소공배수이다. 

LCM (Least Common Multiple) = n * m // GCD(Greatest Common Divisior)