How to Find Divisors of a Number?

A number that equally divides a larger integer is referred to as a divisor or factor. By simply listing all the possible methods to multiply two numbers together to obtain a small integer, it is simple to discover how many divisors that integer has. When dealing with larger integers, figuring out how many divisors there are becomes more difficult. So, we are going to build a program to find all the divisors of a particular number or an integer. We are also going to calculate the Time complexity and the Space complexity of the program also.

Approach for the Program

One simple approach would be to cycle through all the integers from 1 to n, testing each one to see if it divides n before printing it. Below is a program for the same.

Example 1:

// C++ implementation of Naive method to print all
// divisors
#include <iostream>
using namespace std;


// function to print the divisors
void printDivisors(int n)
{
	for (int i = 1; i <= n; i++)
		if (n % i == 0)
			cout <<" " << i;
}


/* Driver program to test above function */
int main()
{
	cout <<"The divisors of 100 are: \n";
	printDivisors(100);
	return 0;
}

Output:

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

Time Complexity for the following program is - O(n)

The Space Complexity for the following program is - O(1)

Approach 2

All the divisors will be represented in pairs if we pay close attention. The different pairings of divisors, for instance, are (1,100), (2,50), (4,25), and (5,20) if n = 100. (10,10). We could considerably speed up our program by using this fact. However, if there are two equal divisors, as there are in the case of (10, 10). We would just print one of them in this scenario.

Example 2:

// A Better (than Naive) Solution to find all divisors
#include <iostream>
#include <math.h>
using namespace std;


// Function to print the divisors
void printDivisors(int n)
{
	// Note that this loop runs till square root
	for (int i=1; i<=sqrt(n); i++)
	{
		if (n%i == 0)
		{
			// If divisors are equal, print only one
			if (n/i == i)
				cout <<" "<< i;


			else // Otherwise print both
				cout << " "<< i << " " << n/i;
		}
	}
}


/* Driver program to test above function */
int main()
{
	cout <<"The divisors of 100 are: \n";
	printDivisors(100);
	return 0;
}

Output:

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

Time Complexity for the following program is -  O(sqrt(n))

Space Complexity for the following program is - O(1)

Approach 3

In the method below, we first print the only numbers that have a remainder of 0, and then, after we leave the loop, we only display the quotient of numbers that has a remainder of 0. If we look at the results we obtained, we can see that the divisors are displayed in a zigzag pattern (small, large pairs). So long as we store half of them, we can print them in sorted order. The if condition is used between the two loops when the corner factors in the loops condition differ by 1 (for example, factors of 30 (5,6)here, 5 would be printed twice); this step is necessary to fix the problem. let's clarify this using an example.

Example 3:

#include <iostream>
#include <math.h>
using namespace std;


// Function to print the divisors
void printDivisors(int n)
{
	int i;
	for (i = 1; i * i < n; i++) {
		if (n % i == 0)
			cout<<i<<" ";
	}
	if (i - (n / i) == 1) {
		i--;
	}
	for (; i >= 1; i--) {
		if (n % i == 0)
			cout<<n / i<<" ";
	}
}


// Driver code
int main()
{
	cout << "The divisors of 100 are: \n";


	printDivisors(100);


	return 0;
}

Output:

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

Time Complexity for the following program is - O(sqrt(n))

Space Complexity for the following program is - O(1)