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