Problem Statement: Find all factors of a number or find all distinct divisors of a natural number.
Examples:
Example 1: Input: n = 6 Output: 1,2,3,6 Explanation: 6 is divisible by 1,2,3,6 Example 2: Input: n = 9 Output: 1,3,9 Explanation: 9 is divisible by 1,3,9
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution1: Brute force
Intuition: We can simply use a for loop from 1 to n and check for every element that n is divisible by it or not, if it is then we will print it otherwise just skip it.
Approach:
- Use a for loop from 1 to n.
- If n is divisible by any element of the loop then print it.
- Otherwise skip it.
Code:
C++ Code
#include <iostream>
using namespace std;
void Divisor(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
cout <<" " << i;
}
int main()
{ int n = 6;
cout <<"Factors of "<<n<<" are: ";
Divisor(n);
return 0;
}
Output: Factors of 6 are: 1 2 3 6
Time Complexity: O(N)
Space Complexity: O(1)
Java Code
import java.util.*;
public class tuf {
static void Divisor(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}
public static void main(String args[])
{ int n = 6;
System.out.print("Factors of " + n + " are: ");
Divisor(n);
}
}
Output: Factors of 6 are: 1 2 3 6
Time Complexity: O(N)
Space Complexity: O(1)
Solution2: Optimised approach
Intuition: When we thoroughly see the factors of a natural number, they always lie in pairs. For if ‘n’ is divisible by any number ‘i’ then it will also be divisible by its quotient of n/i.
Approach:
- Run a for loop from 1 to SquareRoot of n.
- If n is divisible by any number i then the quotient of n/i is also divisible by n, print both i and n/i.
- Take care of the edge case when n/i=i, print only i one time, to remove duplicates.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
void Divisor(int n)
{
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;
}
}
}
int main()
{ int n = 14;
cout <<"Factors of "<<n<<" are: ";
Divisor(n);
return 0;
}
Output: Factors of 14 are: 1 14 2 7
Time Complexity: O(sqrt(N))
Space Complexity: O(1)
Java Code
import java.util.*;
public class tuf {
static void Divisor(int n)
{
for (int i=1;i<=Math.sqrt(n); i++)
{
if (n%i==0)
{
// If divisors are equal, print only one
if (n/i == i)
System.out.print(" "+ i);
else // Otherwise print both
System.out.print(i+" " + n/i + " " );
}
}
}
public static void main(String args[])
{ int n = 14;
System.out.print("Factors of " + n + " are: ");
Divisor(n);;
}
}
Output: Factors of 14 are: 1 14 2 7
Time Complexity: O(sqrt(N))
Space Complexity: O(1)
Special thanks to Prashant Sahu for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article