이번 글에서는 숫자 n을 입력받아, 1부터 n까지의 모든 숫자로 정확히 나누어 떨어지는 가장 작은 수를 찾아 반환하는 JavaScript 함수를 작성해 보겠습니다.
수학적으로 이 문제는 1부터 n까지의 최소공배수(LCM)를 구하는 것과 같습니다. 예를 들어 n이 10이라면, 1부터 10까지 모든 수로 나누어 떨어지는 가장 작은 수는 2520입니다.
접근 방법
가장 효율적인 방법은 소인수분해를 활용하는 것입니다. 핵심 아이디어는 다음과 같습니다.
- n 이하의 각 소수 p에 대해, p의 거듭제곱 중 n보다 작거나 같은 가장 큰 값을 구합니다.
- 이 값들을 모두 곱하면 1부터 n까지의 최소공배수가 됩니다.
예를 들어 n = 20일 때, 소수 2에 대해서는 2⁴ = 16이 20 이하인 가장 큰 거듭제곱이고, 소수 3에 대해서는 3² = 9, 소수 5와 7, 11, 13, 17, 19에 대해서는 각각 그 수 자체가 됩니다. 이들을 모두 곱하면 답을 얻을 수 있습니다.
코드 구현
다음은 위 접근 방식을 구현한 코드입니다.
const smallestDivisible = (num) => {
let i, n = 1;
// n 이하에서 num보다 크지 않은 n의 가장 큰 거듭제곱을 구하는 함수
const largestPower = (n, num) => {
let p, e = 2, largest = n;
while ((p = Math.pow(n, e)) <= num) {
largest = p;
e += 1;
}
return largest;
}
// 소수 판별 함수
const isPrime = n => {
let i, num = Math.ceil(Math.sqrt(n));
for (i = 3; i <= num; i += 2) {
if (n % i === 0) {
return false;
}
}
return true;
}
// 홀수 소수들에 대해 가장 큰 거듭제곱을 곱해 나감
for (i = 3; i <= num; i += 2) {
if (isPrime(i)) {
n *= largestPower(i, num);
}
}
// 마지막으로 2의 가장 큰 거듭제곱을 곱함
return n * largestPower(2, num);
}
console.log(smallestDivisible(20));실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
232792560
즉, 1부터 20까지의 모든 숫자로 나누어 떨어지는 가장 작은 수는 232,792,560입니다.
코드 설명
- largestPower(n, num): n의 거듭제곱 중 num보다 작거나 같은 가장 큰 값을 반환합니다. 예를 들어 largestPower(2, 20)은 16을 반환합니다.
- isPrime(n): 제곱근까지만 검사하고 홀수만 확인하여 소수 여부를 판별합니다. 짝수는 별도로 처리되므로 검사 범위를 줄여 성능을 높였습니다.
- 메인 루프: 3부터 num까지 홀수만 순회하며 소수인 경우 해당 소수의 가장 큰 거듭제곱을 누적으로 곱합니다. 마지막에 2의 거듭제곱을 곱해 최종 결과를 완성합니다.
이 방법은 단순히 1부터 차례대로 최소공배수를 계산하는 방식보다 연산 횟수가 적어, n이 커져도 효율적으로 동작합니다.