## Tuesday, March 8, 2016

### Find all divisors of a natural number

Find all divisors of a natural number | Set 1 - GeeksforGeeks
Given a natural number n, print all distinct divisors of it.

``` Input:  n = 100
Output: 1 2 4 5 10 20 25 50 100```
Note that this problem is different from finding all prime factors.
If we look carefully, all the divisors are present in pairs. For example if n = 100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10)
Using this fact we could speed up our program significantly.
We, however have to be careful if there are two equal divisors as in case of (10, 10). In such case we’d print only one of them.
Time Complexity : O(sqrt(n))
`void` `printDivisors(``int` `n)`
`{`
`    ``// Note that this loop runs till square root`
`    ``for` `(``int` `i=1; i<=``sqrt``(n)+1; i++)`
`    ``{`
`        ``if` `(n%i==0)`
`        ``{`
`            ``// If divisors are equal, print only one`
`            ``if` `(n/i == i)`
`                ``printf``(``"%d "``, i);`
`            ``else` `// Otherwise print both`
`                ``printf``(``"%d %d "``, i, n/i);`
`        ``}`
`    ``}`
`}`

`void` `printDivisors(``int` `n)`
`{`
`    ``for` `(``int` `i=1;i<=n;i++)`
`        ``if` `(n%i==0)`
`            ``printf``(``"%d "``,i);`
`}`
http://www.geeksforgeeks.org/find-all-divisors-of-a-natural-number-set-2/
Yes! the output is not in a sorted fashion which we had got using brute-force technique.
How to print the output in sorted order?
If we observe the output which we had got, we can analyze that the divisors are printed in a zig-zag fashion (small, large pairs). Hence if we store half of them then we can print then in a sorted order.
`void` `printDivisors(``int` `n)`
`{`
`    ``// Vector to store half of the divisors`
`    ``vector<``int``> v;`
`    ``for` `(``int` `i=1;i<=``sqrt``(n)+1;i++)`
`    ``{`
`        ``if` `(n%i==0)`
`        ``{`
`            ``if` `(n/i == i) ``// check if divisors are equal`
`                ``printf``(``"%d "``, i);`
`            ``else`
`            ``{`
`                ``printf``(``"%d "``, i);`

`                ``// push the second divisor in the vector`
`                ``v.push_back(n/i);`
`            ``}`
`        ``}`
`    ``}`

`    ``// The vector will be printed in reverse`
`    ``for` `(``int` `i=v.size()-1; i>=0; i--)`
`        ``printf``(``"%d "``, v[i]);`
`}`