Getting the divisors count of an integer

Question

I am using mod and my code works. I am wondering if there is a more efficient way to write a method that returns the total number of divisors for an integer.

function getDivisorsCnt(n){
    var divisors = 0;
    mod = n;
    while (mod > 0){
      if(n % mod === 0){
        divisors++;
      }
      mod--;
    }
    return divisors;
}

Answer 1

Some general remarks:

• Variables should be declared explicitly with var, otherwise you create a global variable.
• The indent amount is different between the first level and the deeper levels.
• The spacing is not consistent: while ( vs if(. Generally I would insert a space at least after keywords, and around parentheses/braces etc.

Your implementation is correct but not efficient, as the number of loop iterations and remainder operations is equal to the input number.

The count of divisors can be efficiently computed from the prime number factorization: If $$ n = p_1^{e_1} \, p_2^{e_2} \cdots p_k^{e_k} $$ is the factorization of \$ n \$ into prime numbers \$ p_i \$ with exponents \$ e_i \$, then $$ \sigma_0(n) = (e_1+1)(e_2+1) \cdots (e_k+1) $$ is the number of divisors of \$ n \$, see for example Wikipedia: Divisor function. Example: $$ 720 = 2^4 \cdot 3^2 \cdot 5^1 \Longrightarrow \sigma_0(720) = (4+1)(2+1)(1+1) = 30 \, . $$

An implementation in JavaScript would be

function getDivisorsCnt(n){

    var numDivisors = 1;
    var factor = 2; // Candidate for prime factor of `n`

    // If `n` is not a prime number then it must have one factor
    // which is <= `sqrt(n)`, so we try these first:
    while (factor * factor <= n) {
        if (n % factor === 0) {
            // `factor` is a prime factor of `n`, determine the exponent:
            var exponent = 0;
            do {
                n /= factor;
                exponent++;
            } while (n % factor === 0)
            // `factor^exponent` is one term in the prime factorization of n,
            // this contributes as factor `exponent + 1`:
            numDivisors *= exponent + 1;
        }
        // Next possible prime factor:
        factor = factor == 2 ? 3 : factor + 2
    }

    // Now `n` is either 1 or a prime number. In the latter case,
    // it contributes a factor 2:
    if (n > 1) {
        numDivisors *= 2;
    }

    return numDivisors;
}

As an example, getDivisorsCnt(720) requires 720 remainder operations in your algorithm, but only 8 remainder operations and 6 divisions in this algorithm.

Answer 2

There definitely is a more efficient way to count a value's divisors.

We know that a number's square root multiplied by itself is the largest possible divisor besides itself, so we cut the number of divisors we check in half.

function getDivisorsCount(n) {
    // 1 is a special case where "1 and itself" are only one divisor rather than 2
    if (n === 1) {
        return 1;
    }

    var divisors = 2; // acounts for "1 and itself"

    var mod = 2;
    while (mod * mod <= n) {
        if (n % mod === 0) {
            if (mod * mod < number) {
                // mod and number/mod are (different) divisors
                divisors += 2;
            } 
            else {
                // mod == number/mod is a divisor
                divisors += 1; 
            }
        }
        mod++;
    }

    return divisors;
}

As a note, zero and negative numbers are probably also special cases that aren't necessarily handled correctly here.