# Find all divisors of a natural number | Set 2

Given a natural number n, print all distinct divisors of it.

Examples:

``` Input : n = 10
Output: 1 2 5 10

Input:  n = 100
Output: 1 2 4 5 10 20 25 50 100

Input:  n = 125
Output: 1 5 25 125 ```

We strongly recommend to refer below article as a prerequisite.
Find all divisors of a natural number | Set 1

In the above post, we had found a way to find all the divisors in O(sqrt(n)) .

However there is still a minor problem in the solution, can you guess?
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.

Below is a implementation for the same:

## C++

 `// A O(sqrt(n)) program that prints all divisors ` `// in sorted order ` `#include ` `using` `namespace` `std; ` ` `  `// function to print the divisors ` `void` `printDivisors(``int` `n) ` `{ ` `    ``// Vector to store half of the divisors ` `    ``vector<``int``> v; ` `    ``for` `(``int` `i=1; i<=``sqrt``(n); 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]); ` `} ` ` `  `/* Driver program to test above function */` `int` `main() ` `{ ` `    ``printf``(``"The divisors of 100 are: n"``); ` `    ``printDivisors(100); ` `    ``return` `0; ` `} `

## Java

 `// A O(sqrt(n)) java program that prints all divisors ` `// in sorted order ` ` `  `import` `java.util.Vector; ` ` `  `class` `Test ` `{ ` `    ``// method to print the divisors ` `    ``static` `void` `printDivisors(``int` `n) ` `    ``{ ` `        ``// Vector to store half of the divisors ` `        ``Vector v = ``new` `Vector<>(); ` `        ``for` `(``int` `i=``1``; i<=Math.sqrt(n); i++) ` `        ``{ ` `            ``if` `(n%i==``0``) ` `            ``{ ` `                ``if` `(n/i == i) ``// check if divisors are equal ` `                    ``System.out.printf(``"%d "``, i); ` `                ``else` `                ``{ ` `                     ``System.out.printf(``"%d "``, i); ` `      `  `                    ``// push the second divisor in the vector ` `                    ``v.add(n/i); ` `                ``} ` `            ``} ` `        ``} ` `      `  `        ``// The vector will be printed in reverse ` `        ``for` `(``int` `i=v.size()-``1``; i>=``0``; i--) ` `             ``System.out.printf(``"%d "``, v.get(i)); ` `    ``} ` ` `  `    ``// Driver method ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``System.out.println(``"The divisors of 100 are: "``); ` `        ``printDivisors(``100``); ` `    ``} ` `} `

## Python3

 `# A O(sqrt(n)) java program that prints  ` `# all divisors in sorted order ` `import` `math  ` ` `  `# Method to print the divisors ` `def` `printDivisors(n) : ` `    ``list` `=` `[]  ` `     `  `    ``# List to store half of the divisors ` `    ``for` `i ``in` `range``(``1``, ``int``(math.sqrt(n) ``+` `1``)) : ` `         `  `        ``if` `(n ``%` `i ``=``=` `0``) : ` `             `  `            ``# Check if divisors are equal ` `            ``if` `(n ``/` `i ``=``=` `i) : ` `                ``print` `(i, end``=``" "``) ` `            ``else` `: ` `                ``# Otherwise print both ` `                ``print` `(i, end``=``" "``) ` `                ``list``.append(``int``(n ``/` `i)) ` `                 `  `    ``# The list will be printed in reverse     ` `    ``for` `i ``in` `list``[::``-``1``] : ` `        ``print` `(i, end``=``" "``) ` `         `  `# Driver method ` `print` `(``"The divisors of 100 are: "``) ` `printDivisors(``100``) ` ` `  `#This code is contributed by Gitanjali `

## C#

 `// A O(sqrt(n)) C# program that  ` `// prints all divisors in sorted order ` `using` `System; ` ` `  `class` `GFG ` `{ ` `// method to print the divisors ` `static` `void` `printDivisors(``int` `n) ` `{ ` `    ``// Vector to store half ` `    ``// of the divisors ` `    ``int``[] v = ``new` `int``[n]; ` `    ``int` `t = 0; ` `    ``for` `(``int` `i = 1;  ` `             ``i <= Math.Sqrt(n); i++) ` `    ``{ ` `        ``if` `(n % i == 0) ` `        ``{ ` `            ``// check if divisors are equal ` `            ``if` `(n / i == i)  ` `                ``Console.Write(i + ``" "``); ` `            ``else` `            ``{ ` `                ``Console.Write(i + ``" "``); ` ` `  `                ``// push the second divisor ` `                ``// in the vector ` `                ``v[t++] = n / i; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// The vector will be ` `    ``// printed in reverse ` `    ``for` `(``int` `i = t - 1; i >= 0; i--) ` `        ``Console.Write(v[i] + ``" "``); ` `} ` ` `  `// Driver Code ` `public` `static` `void` `Main() ` `{ ` `    ``Console.Write(````"The divisors of 100 are: "````); ` `    ``printDivisors(100); ` `} ` `} ` ` `  `// This code is contributed ` `// by ChitraNayal `

## PHP

 `= 0; ``\$i``--) ` `        ``echo` `\$v``[``\$i``] . ``" "``; ` `} ` ` `  `// Driver code ` `echo` ```"The divisors of 100 are: "````; ` `printDivisors(100); ` ` `  `// This code is contributed by mits ` `?> `

Output :

```The divisors of 100 are:
1 2 4 5 10 20 25 50 100 ```

Time Complexity : O(sqrt(n))
Auxiliary Space : O(sqrt(n))