문제 정의
숫자 하나를 입력받아 해당 숫자의 약수(divisor) 개수를 반환하는 JavaScript 함수를 작성해야 합니다.
입력 예시
const num = 30;
출력 예시
const output = 8;
결과가 8인 이유는 30의 약수가 다음과 같이 총 8개이기 때문입니다 −
1, 2, 3, 5, 6, 10, 15, 30
핵심 원리: 소인수분해 활용하기
이 알고리즘은 소인수분해를 기반으로 동작합니다. 어떤 자연수 N을 소수의 거듭제곱 곱으로 나타내면 다음과 같습니다.
N = pa × qb × rc × …
이때 N의 약수 개수는 각 지수에 1을 더한 값들을 모두 곱한 것과 같습니다.
약수 개수 = (a + 1) × (b + 1) × (c + 1) × …
예를 들어 30은 21 × 31 × 51로 분해되므로, 약수의 개수는 (1+1) × (1+1) × (1+1) = 8개가 됩니다.
구현 코드
위 원리를 적용한 전체 코드는 다음과 같습니다 −
const num = 30;
const countDivisors = (num = 1) => {
if (num === 1) return num
let divArr = [[2, 0]]
let div = divArr[0][0]
while (num > 1) {
if (num % div === 0) {
for (let i = 0; divArr.length; i++) {
if (divArr[i][0] === div) {
divArr[i][1] += 1
break
} else {
if (i === divArr.length - 1) {
divArr.push([div, 1])
break
}
}
}
num /= div
} else {
div += 1
}
}
for (let i = 0; i < divArr.length; i++) {
num *= divArr[i][1] + 1
}
return num
}
console.log(countDivisors(num));
실행 결과
8
코드 동작 방식 살펴보기
코드의 흐름을 단계별로 정리하면 다음과 같습니다.
1. divArr 배열에는 [소수, 지수] 형태의 쌍이 저장됩니다.
2. while 루프에서 현재 숫자를 가장 작은 소수부터 차례대로 나누어 떨어질 때마다 해당 소수의 지수를 1씩 증가시킵니다.
3. 나누어 떨어지지 않으면 시도하는 제수(div)를 1씩 늘려가며 새로운 소수를 찾습니다.
4. 소인수분해가 끝나면 각 소수의 지수에 1을 더한 값을 모두 곱해 최종 약수 개수를 반환합니다.
대안: 제곱근을 이용한 간단한 방법
소인수분해 없이 더 직관적으로 구현하고 싶다면, 1부터 √N까지의 수만 검사하면 됩니다. 약수는 항상 쌍(i, N/i)으로 존재하기 때문에 제곱근까지만 확인하면 전체 약수를 모두 찾을 수 있습니다.
const countDivisorsSimple = (num) => {
let count = 0;
for (let i = 1; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
// 완전제곱수인 경우 중복 방지
count += (i === num / i) ? 1 : 2;
}
}
return count;
};
console.log(countDivisorsSimple(30)); // 8두 방법 모두 같은 결과를 반환하지만, 소인수분해 방식은 큰 수에서도 효율적이며 각 소수의 지수 정보까지 얻을 수 있다는 장점이 있습니다. 반면 제곱근 방식은 코드가 단순하여 빠르게 구현하기에 적합합니다.