Total Number of Divisors of a number in O(log n)
We welcome you to read our brand new article today on how to calculate
number of divisors of a number in O(log n).
E.g1.
Input: N = 8
Output: 4
since there are 4 divisors of 8 i.e. ( 1,2,4,8 )
E.g2.
Input: N = 50
Output: 6
since there are 6 divisors of 50 i.e. ( 1,2,5,10,25,50 )
First let us understand naïve way to do this.
1. Naïve Approach – Brute Force:
Naïve Approach is very simple as you may have guessed that we will be
iterating from 1 to that number N,
And in each iteration we will be checking if ‘i’ divides ‘N’, if so we will
be incrementing our count by 1 and repeating this process.
Finally we will output count, as this contains total number of divisors of
a given number N.
Below is the implementation of naïve approach:
Time Complexity: O(N)
2. Optimized Approach:
As always, we will be optimizing our naïve approach by some of our cool
observations.
let’s look at simple example to observe something.
E.g. N = 16 then for this value of N we have total count
of divisors as 5 i.e. (1,2,4,8,16) but
what if we write 16 (i.e. N) in it’s prime factorization form so we have
16 = 2^{4}
as prime factorization of 16,
So if you notice clearly if we have 2^{4} as our number then the
numbers which divides 2^{4} are
2^{0} , 2^{1} , 2^{2} , 2^{3} , 2 ^{4}
Notice closely what these numbers are i.e. 1, 2, 4, 8, 16
Isn’t these number match with what we have written as divisors of 16 in
this example. Cool, now we are making some great observations can you think
of it now?
can’t make observation, don’t worry we will take one more example for clear
understanding,
E.g. N = 20 then for this value of N we have total count
of divisors as 6 i.e. (1,2,4,5,10,20) but
what if we write 20 (i.e. N) in it’s prime factorization form so we have
20 = 2^{2} * 5^{1}
as prime factorization of 20,
So if you notice clearly if we have 2^{2} as our
number then the numbers which divides 2^{2} are 2^{0} , 2^{1} , 2^{2 }and i.e.
( 1 , 2 , 4 )
If we have 5^{1} as our number then the numbers
which divides 5^{1} are 5^{0} , 5^{1} Notice closely what these
numbers are i.e. 1, 5
Isn’t these number present in the divisors of 20 in this example. Cool, now
we are making some great observations from here.
Observation:
If there is only one distinct prime divisor n= p1^{e}^{1}, then there are obviously e1+1
divisors ( 1 , p1 , p1^{2} , …, p1^{e}^{1} ).
If there are two distinct prime divisors n= p1^{e}^{1 }* p2^{e}^{2},
then you can arrange all divisors in form of a tabular.
So, the number of divisors is trivially (e1+1) * (e2+1)
A similar argument can be made if there are more than two distinct prime
factors.
Still confused? Have a look a below explanation:
Finding the number of divisors of n:
· This turns out to be an application of the multiplication principle for
counting things.
· For example, suppose we want to count (or find all of) the divisors of n
= 144.
· Begin by forming the prime factorization of 144: 144 = 2^{4 .} 3 ^{2}.
· So any divisor of 144 must be a product of some number of 2's (between 0 and 4) and some number of 3's (between 0 and 2). So here's a table of the possibilities:

2^{0} 
2^{1} 
2^{2} 
2^{3} 
2^{4} 
3^{0} 
1 
2 
4 
8 
16 
3^{1} 
3 
6 
12 
24 
48 
3^{2} 
9 
18 
36 
72 
144 
· From the table, it's easy to see that there are 5 x 3 = 15 divisors of
144.
· In general, if you have the prime factorization of the number n.
· Then to calculate how many divisors it has, you take all the exponents in
the factorization, add 1 to each, and then multiply these "exponents + 1"s
together.
So, in simple words if you have a number N, then first write it’s prime
factorization and then do multiplication of exponents + 1, of every prime
factor.
i.e. N = P_{1}^{x1} * P_{2}^{x2} * P _{3}^{x3} * …..P_{n}^{xn}
^{
}
is the prime factorization of N, then total number of divisors is given as:
Total Divisors = ( x_{1} + 1 ) * ( x_{2} + 1 ) * ( x _{3} + 1 ) …. ( X_{n} + 1 )
^{
}
where P is Prime number,
^{
}
x is Number of times, p occurs in prime factorization of N
^{
}
Below is the implementation of optimized approach:
Overall Time Complexity : O( NLog(LogN) )
Answering Query : O( LogN )
Note:
here you may find that time overall time complexity of optimized approach
is more than naïve approach but, optimized approach takes logN time to answer each query and that makes optimized
approach a cool and most used once.
It is always better to solve a question after you learn a new concept as it
helps in making concrete concepts.
So, below are problems which are handpicked by Programmers Army to make your
concept more solid which you learned.
1. Problem from Hackerearth: https://www.hackerearth.com/problem/ algorithm/numberofdivisors5/
2. Problem from Spoj:
https://www.spoj.com/problems/
COMDIV/
We highly recommend to solve above problems if you got stuck read editorials for guidance.
References:
https://cpalgorithms.com/algebra/divisors.html
https://www.math.upenn.edu/
~deturck/m170/wk2/numdivisors.html
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding
By Programmers Army 😊