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