**Problem Statement:** Given a number, print all the divisors of the number. A divisor is a number that gives the remainder as zero when divided.

##
**
Examples
**

Example 1:Input:n = 36Output:1 2 3 4 6 9 12 18 36Explanation:All the divisors of 36 are printed.Example 2:Input:n = 97Output:1 97Explanation:Since 97 is a prime number, only 1 and 97 are printed.

**Practice:**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

## Brute Force Approach

## Algorithm / Intuition

**Solution 1:**

**Intuition:**

As we know the divisors of a number will definitely be lesser or equal to the number, all the numbers between 1 and the number, are the possible candidates for the divisors.

**Approach**:

- This is the basic approach. As we know the possible candidates, we iterate upon all the candidates and check whether they divide the actual number.
- If it divides, then it is one of the divisors. Therfore, we print it.
- If it does not divide, then it is not a divisor. We do this for all the candidates.

## Code

```
#include<iostream>
using namespace std;
void printDivisorsBruteForce(int n){
cout<<"The Divisors of "<<n<<" are:"<<endl;
for(int i = 1; i <= n; i++)
if(n % i == 0)
cout << i << " ";
cout << "\n";
}
int main(){
printDivisorsBruteForce(36);
return 0;
}
```

**Output:**

The Divisors of 36 are:

1 2 3 4 6 9 12 18 36

```
import java.util.*;
public class Solution{
public static void main(String[] args){
printDivisorsBruteForce(36);
}
static void printDivisorsBruteForce(int n){
System.out.println("The Divisors of "+n+" are:");
for(int i = 1; i <= n; i++)
if(n % i == 0)
System.out.print(i + " ");
System.out.println();
}
}
```

**Output:**

The Divisors of 36 are:

1 2 3 4 6 9 12 18 36

```
def printDivisorsBruteForce(n):
print("The Divisors of ",n," are:")
for i in range(1,n+1):
if n % i == 0:
print(i,end=" ")
print()
if __name__ == "__main__":
printDivisorsBruteForce(36)
```

**Output:**

The Divisors of 36 are:

1 2 3 4 6 9 12 18 36

```
function printDivisorsBruteForce(n) {
console.log("The Divisors of " + n + " are:");
for (let i = 1; i <= n; i++) {
if (n % i === 0) {
process.stdout.write(i + " ");
}
}
console.log("\n");
}
printDivisorsBruteForce(36);
```

**Output:**

The Divisors of 36 are:

1 2 3 4 6 9 12 18 36

## Complexity Analysis

**Time Complexity:** O(n), because the loop has to run from 1 to n always.

**Space Complexity:** O(1), we are not using any extra space.

## Optimal Approach

## Algorithm / Intuition

**Solution 2:**

**Intuition:**

- The above method takes O(n) time complexity. We can also think of another approach. If we take a closer look, we can notice that the quotient of a division by one of the divisors is actually another divisor. Like, 4 divides 36. The quotient is 9, and 9 also divides 36.
- Another intuition is that the root of a number actually acts as a splitting part of all the divisors of a number.
- Also, the quotient of a division by any divisor gives an equivalent divisor on the other side. Like, 4 gives 9 while dividing 36. See the image below.

**Approach**:

- From the intuition, we can come to the conclusion that we don’t need to traverse all the candidates and if we found a single divisor, we can also find another divisor(Here, we need to be careful, if the given number is a perfect square, like 36, 6 also give 6 as quotient. This is a corner case.)
- By keeping these in mind, it is enough if we traverse up to the root of a number. Whenever we find a divisor, we print it and also print the quotient. If the quotient is the same, we ignore it. Because the root of a perfect square will give the same quotient as itself.
- The quotients are the numbers that are on the other side of the root. So, it’s okay if we stop traversing at the root.
- This approach is more time efficient than the previous one. But the output sequences are not the same. In the previous approach, we get an ordered output unlike here.

## Code

```
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
using namespace std;
void printDivisorsOptimal(int n){
cout<<"The Divisors of "<<n<<" are:"<<endl;
for(int i = 1; i <= sqrt(n); i++)
if(n % i == 0){
cout << i << " ";
if(i != n/i) cout << n/i << " ";
}
cout << "\n";
}
int main(){
printDivisorsOptimal(36);
return 0;
}
```

**Output:**

The Divisors of 36 are:

1 36 2 18 3 12 4 9 6

```
import java.util.*;
public class Solution{
public static void main(String[] args){
printDivisorsOptimal(36);
}
public static void printDivisorsOptimal(int n){
System.out.println("The divisors of "+n+" are:");
for(int i = 1; i <= (int)Math.sqrt(n); i++)
if(n % i == 0){
System.out.print(i + " ");
if(i != n/i) System.out.print(n/i + " ");
}
System.out.println();
}
}
```

**Output:**

The Divisors of 36 are:

1 36 2 18 3 12 4 9 6

```
def printDivisorsOptimal(n):
print("The Divisors of",n,"are:")
for i in range(1, int(n**0.5)+1):
if n % i == 0:
print(i, end=" ")
if i != n/i:
print(int(n/i), end=" ")
print()
if __name__ == "__main__":
printDivisorsOptimal(36)
```

**Output:**

The Divisors of 36 are:

1 36 2 18 3 12 4 9 6

```
function printDivisorsOptimal(n) {
console.log("The Divisors of " + n + " are:");
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
process.stdout.write(i + " ");
if (i !== n / i) {
process.stdout.write(n / i + " ");
}
}
}
console.log("\n");
}
printDivisorsOptimal(36);
```

**Output:**

The Divisors of 36 are:

1 36 2 18 3 12 4 9 6

## Complexity Analysis

**Time Complexity:** O(sqrt(n)), because every time the loop runs only sqrt(n) times.

**Space Complexity: **O(1), we are not using any extra space.

## Video Explanation

Special thanks toPrathap PandSudip Ghoshfor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article