[알고리즘 공부] 최대공약수와 최소공배수 및 유클리드 호제법

최대공약수 GCD (Greatest Common Divisor)

두 자연수가 공통으로 가지는 약수들 중 가장 큰 값을 의미한다.

 

최소공배수 LCM (Least Common Multiple)

두 자연수의 배수들 중에서 가장 작은 값을 의미한다.

참고로 최소공배수는 최대공약수를 활용하여 바로 구할 수 있다.

최소공배수 = 두 자연수의 곱 / 최대공약수

 

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 

호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

2개의 자연수 a,b에 대해 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 말로는 어떤 말인지 감이 안잡히니 아래 표를 보도록 하자.

 

a를 24, b를 18이라고 했을때,

	GCD	a	b	a%b
1회	GCD(24,18)	24	18	6
2회	GCD(18,6)	18	6	0

2번째 시도만에 나머지가 0으로 만들어졌으니, 이때 나누는 수는 6. 즉, 6이 최대공약수가 된다.

 

해당 방법을 통해 최대공약수와 최소공배수를 더욱 쉽게 구할 수 있다.