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

Python 에서 최대공약수와 최소공배수를 구할 수 있는 방법은 다양하게 존재한다.

그 중에서도 최소 시간을 이용할 수 있는 "유클리드 호제법" 에 대해 알아보고자 한다.

 

유클리드 호제법 (Euclidean Algorithm) 또는 유클리드 알고리즘이라고 불리는 이 방법은 2개의 자연수 또는 정수의 최대 공약수와 최소 공배수를 구할 수 있는 방법이다.

 

• 호제법 : 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 방법

 

예를 들어 a, b (단, a>b) 인 두 수가 존재할 때, a를 b로 나눈 나머지를 r 이라고 하면 a 와 b의 최대공약수는 b와 r의 최대공약수와 같다.

계속해서 나머지를 구해가면서 최종적으로 나머지로 나누어 떨어질때 까지 나누면 되는데 (최종적으로 나누어 떨어진 나머지가 최대공약수가 된다.) 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때의 나누는 수가 a와 b의 최대공약수이다.

 

아래 예제를 보면 보다 이해가 쉽다.

유클리드 호제법 예제

 

이를 파이썬 코드로 구현해보면 아래와 같다. 

 

최대공약수

def gcd(m, n) :
	while n != 0 :
    	r = m % n 
        (m, n) = (n, r)
    return abs(m)

 

앞선 설명대로, m % n 을 나눈 나머지 r을 구하고 나눈수의 나머지를 계속 업데이트 해가며 최종적인 m을 구한다. (n이 0일 때 자동으로 break)

 

---

내용 추가) 

유클리드 호제법을 이용하여 재귀함수를 실습 해 볼 수도 있다.

def gcd(a, b):
	if a % b == 0 :
    	return b
    else : 
    	return gcd(b, a % b)
        
print(gcd(192, 162))

 

1. a가 b의 배수라면 b를 반환한다.

2. 그렇지 않다면 b와 a % b 의 값을 비교하여 (배수 여부를 확인하고) 값을 return

---

 

이제 이를 바탕으로 최소공배수를 구해보자.

 

이때는 이 조건을 기억해두면 좋다.

"두 수 a, b의 최소공배수는 a, b의 곱을 a, b의 최대공약수로 나눈것과 같다."

 

우리가 위에서 유클리드 호제법을 통해 a, b의 최대공약수를 구해주었으므로, 구한 최대공약수 함수를 응용하면 된다.

 

최소공배수

def lcm(m, n) :
	result = (m, n) // gcd(m, n)
    return result

 

간단하다.

 

이를 이용해서 적은 메모리로 최대공약수와 최소공배수를 구할 수 있다.