Javascript 최대공약수(GCD), 최소공배수(LCM)

 최대공약수(Greatest Common Divisor)

 : 두 수 이상의 수의 공통인 약수 중 가장 큰 수

 

최소공배수(Least Common Multiple)

: 두 수 이상의 수의 공통인 배수 중 가장 작은 수

 

 

최대공약수와 최소공배수를 구할 때 유클리드 호제법을 이용한다.

유클리드 호제법(Euclidean algorithm)

: 두 양의 정수 a, b (a > b)에 대하여 a = bq + r(0 ≦ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, r = 0 이라면, a, b의 최대공약수는 b가 된다. 

 

유클리드 호제법을 이용하여 최대공약수를 구하는 소스코드는 다음과 같다.

// 최대공약수
function GCD(a, b) {
 var r = a % b;
 if(r == 0){
   return b;
 }
 return GCD(b, r)
}

// 숏코드
const GCD = (a, b) => a % b === 0 ? b : GCD(b, a % b)

 

최소공배수는 a * b = 최대공약수 * 최소공배수를 활용하여 구한다. 즉, 다음과 같이 구할 수 있다.

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