유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구할 때 사용하는 알고리즘이다. 일반적으로 두 수의 최대공약수를 구하려면 일단 두 수를 소인수분해한 후 공통된 소수 중 가장 큰 수를 찾으면 된다. 그러나 수가 커질수록 소인수분해하기 어렵기 때문에 유클리드 호제법을 사용하면 쉽고 효율적으로 구할 수 있다.

구현 방법

유클리드 호제법의 개념은 다음과 같다. 

두 자연수 a와 b (a > b), 그리고 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b 와 r의 최대공약수와 같다.
GCD(a, b) = GCD(b, r)

위와 같은 방법을 반복해서 r이 0이 될 때 b가 최대공약수가 된다. 이 알고리즘의 시간복잡도는 O(log N)이 된다.

재귀 함수를 사용하면 쉽게 구현할 수 있다.

//javascript 코드
function GCD(a, b){
  if(a % b == 0){
  	return b;
  }
  else {
  	return GCD(b, a%b);
  }
}

최소공배수

최대공약수를 구했다면 최소공배수는 다음과 같이 쉽게 계산할 수 있다.

최소공배수 = (a * b) / GCD(a,b)