Video credits : mycodeshool

You'll learn how to find all factors of a number in this tutorial.

Given a number n which is a natural number, we want to find out all its factors.

For example, if n is lets say 12, then its factors are 1 and 1 divides all natural numbers. 2, 3, 4 , 6 and 12. So, 12 has 6 factors in all.

These 6 numbers divide 12. Ok, so if we have n = 17, we will have only two factors - 1 and 17. That's because 17 is a prime number. If n is 36, then the factors would be 1,2, 3, 4, 6, 9 , 12 , 18 and 36. So, there are 9 factors of 36. So, how do we solve this problem programatically.

The simplest approach is trial division. What we can do is we can try dividing n by all numbers starting 1 to n and find out all the factors. So, algorithm would go like lets say we start with an empty list named A and then we run a loop starting 1 all the way till n.

So, for i starting 1 to n, if i divides n or in other words n modulo i is 0, then we add i to list A.

So, once we exit this loop, the list A has all the factors of n. Now, there is a simple observation here.

A number is always divided by 1 and itself. Apart from 1 and itself, the smallest factor that it can have is 2 and the largest factor that it can have will be n/2.

There would be no factor of n other than n itself after n/2. So, we can improve this algorithm a little here. What we can do is lets say instead of starting with an empty list we start with 1 and n already in the list and then we can run our loop through 2 to n/2. We do not run the loop all the way till n.

This is definitely better than running loop till n. Now, what will be the running time of this algorithm. We have a loop running till n/2. So, the time taken is proportional to n which in other words, we also say that this is big-oh of n in terms of time complexity. Can we do something better than this.

Well,, lets see. As we know and as we had discussed in our previous lessons on primality testing also, if there is a number a that divides number n, then there is another number b equal n/a that also divides n. The factors of a number always exist in pair and we call them co-factors.

We always have a relationship like a*b = n. For example, if we pick up the case of 36 here, then if a =1, then b = 36/1 which is 36. if a is 2, b would be 18. if a is 3, b would be 12. if a is 4, b would be 9. And if a is 6, then b is also equal to 6. This happens only when a is square root of n, so in this case 6 is square root of 36.

So, in the case when a is not equal to b, and lets say if a is the smaller one in the pair, if a < b, then a is less than square root of n and b is always greater than square root of n. And if a is equal to b like in the case of 6 here, then they are both equal to square root of n.

We can use this property to improve our algorithm. So, what we can do now is we can again start with an empty list and we can run the loop from 1 to square root of n, so we say for i starting 1 to square root of n, if i divides n , or if n modulo i is 0, then we add i to list a and we also add n upon i to list A. So, this will be our a and this will be our b.

Ok, we could have chosen to start with 1 and n in the list initially only, then we would be running the loop starting 2, but if we are running the loop starting 1, then 1 and n will also come into the list in the loop itself. Now, there still is one issue with this code. We have not handled the case when a =b, so when a is equal to b, using this algorithm we will add the factor twice in the list.

So, we need to only a little change to handle this. We need to say that if i is not equal to square root of n, which will be the case when a will be equal to b, then only add n/i to list A. As we know when, the co-factors are equal, then the factor is square root of n.

Now, a couple of things here. I have only written a pseudo-code. In an actual program, A can be an array or A can be any other dynamic list available in your language like vector in C++.

When we are adding the elements, we are not adding them in a sorted order. So, the factors in the list will not appear in an increasing order. If we want a sorted list, then we need to do some modifications to the algorithm to add the factors in a sorted manner.

I leave that as an exercise for you. Ok, so what will be the running time or the time complexity of this algorithm. We have a loop running 1 to square root of n. So, clearly the time taken here is proportional to square root of n. We have just one loop running till square root of n.

Or in other words, this is big-oh of square root of n in terms of big oh notation. The time complexity is O(sqrt(n)). big-oh of square root of n is a lot lot lot better than O(n) algorithm, any big-oh of n algorithm. So, this was finding out all the factors of a number. In the next lesson, we will see algorithm to find out prime factorization of a number.