자바스크립트로 숫자의 약수 개수 구하기

약수 개수 세기 문제란?

주어진 숫자를 나누어 떨어지게 만드는 수, 즉 약수(divisor)의 개수를 반환하는 자바스크립트 함수를 작성하는 것이 목표입니다.

예를 들어 입력값이 12라면, 12의 약수는 다음과 같습니다.

1, 2, 3, 4, 6, 12

따라서 출력 결과는 6이 되어야 합니다.

기본 풀이 코드

const num = 12;

const countFactors = num => {
    let count = 0;
    let flag = 2;
    while(flag <= num / 2){
       if(num % flag++ !== 0){
          continue;
       };
       count++;
    };
    return count + 2;
};

console.log(countFactors(num));
console.log(countFactors(2));
console.log(countFactors(454));
console.log(countFactors(99));

실행 결과

6
2
4
6

코드 동작 원리

• flag는 2부터 시작: 1은 모든 수의 공통 약수이므로 검사할 필요가 없습니다.
• 반복 범위는 num / 2까지: 어떤 수의 절반보다 큰 약수는 그 수 자신뿐이기 때문입니다.
• 나머지 연산으로 판별: num % flag === 0이면 flag는 num의 약수이므로 count를 1 증가시킵니다.
• count + 2 반환: 검사에서 제외된 1과 num 자신, 두 개의 약수를 마지막에 더해줍니다.

더 빠른 방법: 제곱근 활용

위 방식의 시간 복잡도는 O(n)입니다. 하지만 약수는 항상 쌍을 이루기 때문에(예: 3 × 4 = 12), 제곱근까지만 검사하면 O(√n)으로 최적화할 수 있습니다.

const countFactorsFast = num => {
    let count = 0;
    for(let i = 1; i * i <= num; i++){
       if(num % i === 0){
          // 완전제곱수(i² == num)인 경우는 한 번만 카운트
          count += (i * i === num) ? 1 : 2;
       }
    }
    return count;
};

console.log(countFactorsFast(12));  // 6
console.log(countFactorsFast(36));  // 9

12의 경우 1, 2, 3만 검사하면 짝이 되는 약수 12, 6, 4가 자동으로 계산됩니다. 이처럼 제곱근 방식은 숫자가 커질수록 성능 차이가 극적으로 벌어지므로, 실무에서는 최적화된 버전을 사용하는 것이 좋습니다.