[알고리즘] 유클리드 호제법이란?

유클리드 호제법

유클리드 호제법에서 호제법이란 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘이다.

알고리즘에서는 최대 공약수를 얻는데 사용된다.

 

개념

정수 A, B가 주어지는 경우 A와 B의 최대 공약수는 A를 B로 나눈 나머지를 R이라고 할 때 B 와 R의 최대 공약수와 같다.

여기서 B와 R의 최대 공약수 역시 B를 R로 나눈 나머지를 R2라고 할 때  R과 R2의 최대 공약수와 같다. 이런식으로 재귀적으로 숫자를 줄여갈 수 있으며 나머지가 0이 될 때 마지막으로 숫자를 나눈 값이 최대 공약수이다.

 

R = A % B

R2 = B % R

R3 = R % R2 .... 0 = Rx % Rx-1 

최대 공배수는 Rx-1이 된다. 

 

코드로 표현

최소 공배수는 최대 공약수만 알면 쉽게 구할 수 있다.

A, B가 주어질 때, G는 최소 공배수

 

A = G * x 

B = G * y

 

최대 공약수는 G * x * y

따라서 최대 공약수는

G * x * y = (A * B)/G

A와 B의 곱을 최소 공배수로 나눈 것과 같다.