# Finding all the factors of a given number

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