Print all Divisors of a given Number

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 = 36
Output: 1 2 3 4 6 9 12 18 36
Explanation: All the divisors of 36 are printed.

Example 2:
Input: n = 97
Output: 1 97
Explanation: 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 Optimal Approach

Expand any one approach by clicking the given options in the bar. Clicking one approach on bar, closes all other expands. You can manually expand more than one approach at a time

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 to Prathap P and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article