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 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.

Solution

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

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:

C++ 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

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.

Java Code

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

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.

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 divison 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 a 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 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 upto the root of a number. Whenever we find a divisor, we print it and also print the quotient. If the quotient is same, we ignore it. Because, root of a perfect square will give same quotient as itself.
  • The quotients are the numbers that are on the other side of the root. So, its okay if we stop traversing at root.
  • This approach is time efficient than the previous one. But the output sequences are not same. In the previous approach, we get an ordered output unlike here.

Code:

C++ Code

#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

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

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

Java Code

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

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

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

Special thanks to Prathap P for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article