C++ Program to Display Factors of a Number

In the previous article, we have discussed about C++ Program to Check Whether a Number is Armstrong or Not. Let us learn how to Display Factors of a Number in C++ Program.

Methods to display factors of a number in c++

In this article, we discuss different methods of how we can display factors of a number in c++. The methods that we will discuss are given below.

First of all, let’s understand what a factor of a number is. Factors of a number are that number that completely divides the given number. For example factors of 100 are 1 2 4 5 10 20 25 50 100 because all these numbers can divide 100 completely. Now we will discuss different methods to display factors of a number.

Method 1-Using loop with O(n) complexity

Here the basic approach that we will follow is that we iterate a loop from 1 to the given number and print that number which completely divides the given number. Let’s write code for this.

#include <iostream>
using namespace std;

void printFactors(int n)
{
    for (int i = 1; i <= n; i++)
        if (n % i == 0)
            cout <<" " << i;
}

int main()
{
    int n=100;
    cout <<"The divisors of "<<n<<" are: \n";
    printFactors(100);
    return 0;
}

Output

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

This method has a time complexity of O(n). We can improve this complexity by some analysis which we will see in the next method.

Method 2-Using loop with O(sqrt(n)) complexity

If we look carefully, all the divisors are present in pairs. For example if n = 100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10). So instead of running the loop from 1 to the given number n, we can decrease its iteration to sqrt(n) because after this iteration we will get all the factors. We, however, have to be careful if there are two equal divisors as in the case of (10, 10). In such a case, we’d print only one of them. This will reduce the complexity from O(n) to O(sqrt(n)). Let’s write code for this.

#include <bits/stdc++.h>
using namespace std;

void printFactors(int n)
{
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            if (n/i == i){
                cout <<" "<< i;
            }
 
            else{
                cout << " "<< i << " " << n/i;
            }
        }
    }
}

int main()
{
    int n=100;
    cout <<"The divisors of "<<n<<" are: \n";
    printFactors(100);
    return 0;
}

Output

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

So these are the methods to display factors of a number in c++.