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);