Factors of a Given Number - Tutorial [Updated]

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