Given a number, how do we write a program to find all of it’s factors or divisors.
For example, for the number 18, the factors are {1, 2, 3, 6, 9, 18}.
An immediate algorithm that comes to our mind is to run a loop from 1 to n. In each iteration check if the counter divides the number n. If it divides print it.
for( i = 1; i <= n; i++ )
{
if( n % i == 0 )
cout << i << " ";
}
But this approach runs for n iterations. we can do better than this. One possible improvement can be to start with 1 and n as factors and run the loop from 2 to n/2. This is based on the observation that after n/2 there will not be any factors of n until n. So it is safer to stop at n/2 itself.
list.add(1);
for( i = 2; i <= n/2; i++ )
{
if( n % i == 0 )
list.add(i);
}
list.add(n);
This is clearly an improvement over the previous method because it runs only for n/2 iterations. Can we still improve this?
Yes it is possible! This is based on the observation that the factors always appear in pairs. If a is a factor of n, then there should be some k such that a * k = n. so k must also be a factor of n. This approach runs only for sqrt(n) iterations and performs better than the previous two algorithms.
factorList.add(1);
for( i = 2; i <= sqrt(n); i++ )
{
if( n % i == 0 )
{
factorList.add(i);
if( i != sqrt(n) )
factorList.add(n/i);
}
}
factorList.add(n);