Number of Divisors of an Integer

Problem

Given an integer $N$, find its number of divisors.

For example, $12$ has the following divisors $1,2,3,4,6$ and $12$. So its number of divisors is $6$.

Number Of Divisors Function: $NOD(N)$ or $\sigma_{0}(N)$

Number of Divisors of N is also called $\sigma_{0}(N)$. That’s just a fancy way of asking for the number of divisors of N. You can read more on it from Wiki. I will refer to Number of Divisors of $N$ as either $\sigma_0(N)$ or $NOD(N)$. They both mean same.

Brute Force Method O(N)

Anyways, what is the easiest way to find Number of Divisors (NOD)? We can try to divide $N$ with all numbers from $1-N$ and keep count of how many of those numbers divide $N$. This will definitely work, but obviously we need to do better.

Optimized to O($\sqrt{N}$)

In “Primality Test – Naive Methods, we established that if we can write $N=A \times B$, then one of ${A,B}$ must be $<=\sqrt{N}$.

So using that same idea we can find NOD by simply looping till $\sqrt{N}$ and check if that particular number divides $N$. If it doesn’t then it is not a divisor and if it does then we found a ${A,B}$ pair of divisors. If $A \neq B$, then we add $2$ to result, otherwise we add $1$.

Examples

Suppose $N=24$. We need to loop till $\lfloor {\sqrt{24}} \rfloor= 4$. We get the following pairs of divisors, ${1,24}, {2,12}, {3,8}, {4,6}$. So our answer is $8$.

Let’s try again with $N=36$. We need to loop till $\lfloor {\sqrt{36}} \rfloor= 6$. We get the following pairs of divisors, ${1,36}, {2,18}, {3,12}, {4,9}, {6,6}$. So our answer is $9$. Notice that the last pair does not satisfy the condition $A \neq B$. So we add one for that pair.

This brings out an interesting observation. NOD of $N$ is always even except for when $N$ is a perfect square.Because whenever $N$ is perfect square, $\sqrt{N}$ would be its divisor and it will form a pair with itself.

Code Using Loop till $\sqrt{N}$

int NOD ( int n ) {
    int res = 0;
    int sqrtn = sqrt ( n );
    
    for ( int i = 1; i < sqrtn; i++ ) {
        if ( n % i == 0 ) res += 2; // Found a divisor pair {A,B}
    }
    
    // Need to check if sqrtn divides n
    if ( n % sqrtn == 0 ) {
        if ( sqrtn  sqrtn == n ) res++; // If n is perfect square
        else res += 2; // Not perfect square
    }

    return res;
}

We loop from $1$ to $\sqrt{N}-1$ at line 5. Then at line 10, we handle $\sqrt{N}$ seperately.

Using Prime Factorization

It is possible to find NOD from prime factorization of N. Suppose $N=12$. Its prime factorization is $2^2 \times 3$. Is it possible to divide $12$ with $5$? No. Cause the prime factorization of $12$ does not contain $5$. We can divide $N$ with primes that appear in factorization of $N$.

Next, can we divide $12$ with $2^3$? No. The power of $2$ in prime factorization of $12$ is $2^2$. So we cannot divide $12$ with $2^3$, since $2^2$ is not divisible by $2^3$.

So, if we are trying to divide $N$, that has prime factorization $N=p_1^{a_1} \times p_2^{a_2} \times ...p_x^{a_x} $, then the divisors of $N$, $D$, will have prime factorization of form $D=p_1^{b_1} \times p_2^{b_2} \times ...p_x^{b_x}$, where $b_i <= a_i$.

For example, divisor of $12=2^2 \times 3$ will have prime factorization, $D=2^x \times 3^y$, where $x <= 2, y <= 1$. When $x = 1$ and $y=1$, $D=2^1 \times 3^1=6$ which is a divisor of $12$. If we use a different combination of $[x,y]$, then we get a different divisor. So how many different combination can we use here? We know that, $0<=x<=2$ and $0<=y<=1$. So for $x$ we can use ${0,1,2}$ and for y we can use ${0,1}$. So we can use $3 \times 2=6$ combinations of ${x,y}$. And that is our NOD.

So, if $N=p_1^{a_1} \times p_2^{a_2} \times ...p_x^{a_x}$, then $D=p_1^{b_1} \times p_2^{b_2} \times ...p_x^{b_x}$. We get new divisors for using different combination for ${b_1,b_2...b_x}$. How many different combinations can we make? $(a_1+1) \times (a_2+1) \times...(a_x+1)$. Therefore, $\sigma_0(N) = (a_1+1) \times (a_2+1) \times...(a_x+1)$.

So basically, in order to find NOD, all we need to do is factorize $N$, then take each of its prime factors power, increase them by $1$ and finally multiply all of them. Easy right?

Examples

$N=12=2^2 \times 3$. $NOD(N)= (2+1) \times (1+1) = 6$
$N=15=3 \times 5$. $NOD(N)= (1+1) \times (1+1) = 4$.
$N=252 = 2^2 \times 3^2 \times 7$.
$NOD(N)=(2+1) \times (2+1) \times (1+1) = 18$.

Try out this yourself using other small values of N.

Code Using Prime Factorization

The code for $NOD$ is not very different from the one we used for factorize() in Prime Factorization of an Integer. We just need to modify it slightly to suit our needs.

int NOD ( int n ) {
    int sqrtn = sqrt ( n );
    int res = 1;
    for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) {
        if ( n % prime[i] == 0 ) {
            int p = 0; // Counter for power of prime
            while ( n % prime[i] == 0 ) {
                n /= prime[i];
                p++;
            }
            sqrtn = sqrt ( n );
            p++; // Increase it by one at end
            res = p; // Multiply with answer
        }
    }
    if ( n != 1 ) {
        res = 2; // Remaining prime has power p^1. So multiply with 2/
    }
    return res;
}

I have highlighted the lines that are different from factorize().

Reference

  1. Divisor Function