Number of Divisors of an Integer

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 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;
}

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. 

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()$.

1. Divisor Function - https://en.wikipedia.org/wiki/Divisor_function