약수란?

약수(divisor)란 어떤 정수 N을 나누어떨어지게 하는 수

즉, N을 i로 나눌 때 나머지가 0이 되면 i는 N의 약수이다. 예를 들어 12의 약수에는 1, 2, 3, 4, 6, 12가 있다.

---

자연수 N의 약수의 개수 구하기

1. 모든 수를 검사하는 방법 (O(N))

1부터 N까지 모든 수를 순차적으로 확인하며 N을 나눌 때 나머지가 0이 되면 약수로 카운트하는 방법
이 방법은 가장 간단하지만, 비효율적인 방법이다.

const numberOfDivisors1 = (n) => {
    let count = 0;
    for (let i = 1; i <= n; i++) {  // 1부터 N까지 검사
        if (n % i === 0) count++;   // 약수이면 카운트 증가
    }
    return count;
};

// 예시 사용
console.log(numberOfDivisors1(12)); // 출력: 6 (약수: 1, 2, 3, 4, 6, 12)

이 방식은 O(N)의 시간 복잡도를 가지며 작은 N에 대해서는 문제가 없지만, 큰 수 N에 대해서는 계산 시간이 오래 걸린다는 문제가 있다.

2. N/2까지 검사하는 방법 (O(N/2))

모든 약수가 N의 절반을 초과할 수 없다는 점을 이용하는 방법.
예를 들어, 12의 절반인 6을 초과하는 약수는 12 자체밖에 없으므로 1부터 N/2까지의 수만 검사하고 마지막에 N을 더하면 된다.

const numberOfDivisors2 = (n) => {
    let count = 1;  // N 자체를 미리 약수로 포함 (N > 1일 때만 유효)
    for (let i = 1; i <= n / 2; i++) {  // 1부터 N/2까지 검사
        if (n % i === 0) count++;       // 약수이면 카운트 증가
    }
    return count;
};

// 예시 사용
console.log(numberOfDivisors2(12)); // 출력: 6 (약수: 1, 2, 3, 4, 6, 12)

이 방식은 O(N/2)의 시간 복잡도를 가지며 N이 커질수록 1번의 방법보다 효율적이다.

3. 제곱근까지 검사하는 방법 (O(√N))

자연수 N의 약수를 나열했을 때, N의 제곱근을 기준으로 위아래의 약수 개수가 동일하다는 것을 사용한 방법
따라서 N의 제곱근보다 값이 작은 약수들을 구한 뒤, 그 개수에 2배를 해주면 총 약수 개수를 구할 수 있다.

예를 들어, 36의 약수는 (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)과 같이 쌍을 이루며, 6을 기준으로 대칭을 이룬다. 즉, √N까지만 검사해도 모든 약수를 한 번씩만 카운트할 수 있다.

const numberOfDivisors3 = (n) => {
    let count = 0;
    for (let i = 1; i * i <= n; i++) {   // 1부터 √N까지 검사
        if (i * i === n) count++;        // i가 N의 정확한 제곱근이면 하나만 카운트
        else if (n % i === 0) count += 2; // (i, N / i) 약수 쌍을 각각 카운트
    }
    return count;
};

console.log(numberOfDivisors3(12)); // 출력: 6 (1, 2, 3, 4, 6, 12)

이 방식은 O(√N)의 시간 복잡도를 가지며, 가장 효율적인 방법이다.

---

요약

• 모든 수를 검사: 시간 복잡도 O(N), 가장 단순한 방법으로 1부터 N까지 모두 검사.
• 절반까지만 검사: 시간 복잡도 O(N/2), 약수를 절반까지만 확인하여 효율성 향상.
• 제곱근까지만 검사: 시간 복잡도 O(√N), 약수의 대칭성을 이용해 가장 효율적으로 약수 개수를 구함.