JavaScript로 숫자 범위 내 모든 수의 최소 공배수(LCM) 구하기

이번 글에서는 정확히 두 개의 숫자를 담고 있는 배열을 입력으로 받는 JavaScript 함수를 작성해 보겠습니다. 이 배열은 하나의 숫자 범위를 나타내며, 함수는 해당 범위에 포함된 모든 숫자의 최소 공배수(LCM, Least Common Multiple)를 계산하여 그 결과를 반환해야 합니다.

접근 방식

범위 전체의 최소 공배수를 구하는 가장 효율적인 방법은 최대 공약수(GCD)를 활용하는 것입니다. 두 수 a와 b의 최소 공배수는 다음 공식으로 구할 수 있습니다.

LCM(a, b) = (a × b) / GCD(a, b)

최대 공약수는 유클리드 호제법(Euclidean algorithm)을 재귀 함수로 간단하게 구현할 수 있습니다. 이후 범위의 시작 숫자부터 끝 숫자까지 차례대로 누적 결과와 LCM을 반복 계산하면, 범위 전체의 최소 공배수를 얻을 수 있습니다.

예제 코드

const range = [8, 3];

// 최대 공약수(GCD) - 유클리드 호제법
const gcd = (a, b) => {
   return !b ? a : gcd(b, a % b);
};

// 최소 공배수(LCM)
const lcm = (a, b) => {
   return a * (b / gcd(a, b));
};

// 범위 내 모든 숫자의 최소 공배수 계산
const rangeLCM = (arr = []) => {
   // 시작 값이 끝 값보다 크면 순서를 교환
   if(arr[0] > arr[1]) arr = [arr[1], arr[0]];
   
   let result = arr[0];
   for(let x = arr[0]; x <= arr[1]; x++) {
      result = lcm(x, result);
   }
   return result;
};

console.log(rangeLCM(range));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

840

코드 설명

입력 배열 [8, 3]은 시작 값이 끝 값보다 크므로, 함수 내부에서 먼저 [3, 8]로 순서가 정렬됩니다. 이후 3부터 8까지의 숫자인 3, 4, 5, 6, 7, 8의 최소 공배수를 순차적으로 계산하면 최종 결과인 840이 도출됩니다.

이 방식은 각 단계에서 이전까지의 누적 LCM과 현재 숫자의 LCM만 구하면 되기 때문에, 범위 안의 모든 조합을 일일이 비교하는 것보다 훨씬 효율적입니다.