JavaScript로 1부터 n까지 모든 숫자로 나누어 떨어지는 가장 작은 수 구하기

문제 소개

숫자 n을 입력받아, 1부터 n까지의 모든 숫자로 나누어 떨어지는 가장 작은 수를 찾아 반환하는 JavaScript 함수를 작성해야 합니다.

이 문제는 수학적으로 1부터 n까지의 모든 수의 최소공배수(LCM)를 구하는 것과 동일합니다. 예를 들어 n이 11이라면, 1부터 11까지의 모든 정수로 나눌 수 있는 가장 작은 수는 27720입니다.

예제 코드

다음은 이 문제를 해결하는 코드입니다 −

const num = 11;
const smallestDivisible = (num = 1) => {
   let res = num * (num - 1) || 1;
   for (let i = num - 1; i >= 1; i--) {
      if (res % i) {
         for (let j = num - 1; j >= 1; j--) {
            if (!(i % j) && !(res % j)) {
               res = i * res / j;
               break;
            }
         }
      }
   }
   return res;
}
console.log(smallestDivisible(num));

코드 동작 원리

이 알고리즘은 다음과 같은 단계로 동작합니다:

• 초기 결과값을 num × (num-1)로 설정합니다. 인접한 두 수를 곱하면 대부분의 경우 두 수의 배수를 포함하는 큰 값이 되므로 효율적인 시작점입니다.
• num-1부터 1까지 역순으로 반복하며, 현재 결과값 res가 해당 숫자 i로 나누어 떨어지지 않는지 확인합니다.
• 나누어 떨어지지 않는다면, i와 res의 공통 약수 중 가장 큰 값 j를 찾습니다.
• res에 i를 곱한 뒤 공약수 j로 나누어, 불필요하게 커지지 않으면서도 i의 배수가 되도록 조정합니다. 이것이 바로 최소공배수를 누적 계산하는 과정입니다.
• 모든 반복이 끝나면 res는 1부터 num까지의 모든 수의 최소공배수가 됩니다.

출력 결과

27720

콘솔에는 27720이 출력됩니다. 이 값은 1부터 11까지의 모든 정수(1, 2, 3, ..., 11)로 나누었을 때 나머지가 0이 되는 가장 작은 수입니다.