Link to PDF (Latex Formatted)

Topic : Counting Divisors of a Number

Pre Requisites : Basic Maths , Factorisation , Primality testing

Motivation Problem :

There are T test cases. Each test case contains a number N. For each test case , output the number of factors of N.

1 <  = T <  = 10

1 <  = N <  = 10¹⁸

Note : 1 and N are also treated as factors of the number N.

Solution :

Naive Solution — Factorisation

The most naive solution here is to do the factorisation. But as we can see, it will surely receive the Time Limit Exceeded verdict. You may try to compute the prime numbers till required range and loop over them , but that too exceeds the usual limit of 10⁸ operations. Some optimisations and heuristics may allow you to squeeze through your solution, but usually at the cost of a few TLE's.

Supposing you fit in the above description and cannot think of anything better than the naive solution, I would like to present to you a very simple algorithm which helps you count the number of divisors in , which would be useful for this kind of questions.

Firstly, let's do a quick recap of how we obtain the algorithm for any number N :

We write N as product of two numbers P and Q.

Looping over all values of P gives us the count of factors of N.

Before you move forward to the next section, it would be useful if you try to come up with an algorithm that finds the factors in . As a hint, the way of thinking is same as that of getting to the algorithm.

Factorisation

Let's start off with some maths to reduce our factorisation to :

We write N as product of three numbers P, Q and R.

We can loop over all prime numbers in range and try to reduce N to it's prime factorisation, which would help us count the number of factors of N.

To know how to calculate divisors using prime factorisation, click here.

We will split our number N into two numbers X and Y such that X * Y = N. Further, X contains only prime factors in range and Y deals with higher prime factors (). Thus, gcd(X , Y) = 1. Let the count of divisors of a number N be denoted by the function F(N). It is easy to prove that this function is multiplicative in nature, i.e., F(m * n) = F(m) * F(n), if gcd(M,N) = 1. So, if we can find F(X) and F(Y), we can also find F(X * Y) or F(N) which is the required quantity.

For finding F(X), we use the naive trial division to prime factorise X and calculate the number of factors. Once this is done, we have Y = N / X remaining to be factorised. This may look tough, but we can see that there are only three cases which will cover all possibilities of Y :

1. is a prime number : F(Y) = 2.
2. is square of a prime number : F(Y) = 3.
3. is product of two distinct prime numbers : F(Y) = 4.

We have only these three cases since there can be at max two prime factors of Y. If it would have had more than two prime factors, one of them would surely have been , and hence it would be included in X and not in Y.

So once we are done with finding F(X) and F(Y), we are also done with finding F(X * Y) or F(N).

Pseudo Code :

N = input()
primes = array containing primes till <span class="tex-span">10<sup class="upper-index">6</sup></span>
<span class="tex-span"><i>ans</i> = 1</span>
for all p in primes :
            <span class="tex-span"><i>if</i> <i>p</i> * <i>p</i> * <i>p</i> &gt; <i>N</i></span>:
                  break
            <span class="tex-span"><i>count</i> = 1</span>
            while <span class="tex-span"><i>N</i></span> divisible by <span class="tex-span"><i>p</i></span>:
                  <span class="tex-span"><i>N</i> = <i>N</i> / <i>p</i></span>
            <span class="tex-span"><i>count</i> = <i>count</i> + 1</span>
            <span class="tex-span"><i>ans</i> = <i>ans</i> * <i>count</i></span>
if <span class="tex-span"><i>N</i></span> is prime:
            <span class="tex-span"><i>ans</i> = <i>ans</i> * 2</span>
else if <span class="tex-span"><i>N</i></span> is square of a prime:
            <span class="tex-span"><i>ans</i> = <i>ans</i> * 3</span>
else if <span class="tex-span"><i>N</i> ≠ 1</span>:
            <span class="tex-span"><i>ans</i> = <i>ans</i> * 4</span>

Checking for primality can be done quickly using Miller Rabin. Thus, the time complexity is for every test case and hence we can solve our problem efficiently.

At this point, you may think that in a similar way, we can reduce this to by handling some cases. I have not thought much on it, but the number of cases to be handled are high since after trial division N could be factorised into one, two or three primes. This is easy enough to code in contest environment, which is our prime objective.

This trick is not quite commonly known and people tend to make bugs in handling the three cases. A problem in regionals which uses this trick directly :

Problem F | Codeforces Gym

You can try also this technique on problems requiring factorisation for practice purposes.

Hope you found this useful! Please suggest more problems to be added as well as any edits, if required.

Happy Coding! \end{document}