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.

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. for( i = 1; i <= n; i++ ) { if( n % i == 0 ) cout << i << " "; }

list.add(1); for( i = 2; i <= n/2; i++ ) { if( n % i == 0 ) list.add(i); } list.add(n);

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