C++ Program to Find the Factors of a Number

May 18, 2022

Program to find Factors of a number

To find the answer to a number we will use a loop in which we start dividing the number with 1 up to the number itself and the numbers which perfectly divides the number are the factors.

For Example 100

Factors are: 1, 2, 4, 5, 10, 20, 25, 50, 100

C++ program to find the factors of a number

Different methods

Following are the methods that we will discuss in this post –

  1. Linear traversal between [1, num] to find factors
  2. Linear traversal between [1, √num] to find factors
  3. Using Vector to solve issues caused by the above method
  4. 2 Loop approach to solve without vectors

Method 1

For a user input num

  1. Using loop in the iteration of (i) traverse from [1, num]
  2. Print all values of (i) that divide num perfectly (num % i == 0)

Method 1 Code:-

Run
//C++ Program Factors of a number
#include <bits/stdc++.h>
using namespace std;

//main Program
int main()
{
    int num;
    
    num=100;
    
    cout << "Factors of " << num << " are: " << endl;  
    
    // finding and printing factors b/w 1 to num
    for(int i = 1; i <= num; i++)
    {
        if(num % i == 0)
            cout << i << " ";
    }
}
// Time Complexity: O(N)
// Space Complexity: O(1)

Output

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

Method 2

This method uses observations that all factors come in pairs.

Method 2 Code:-

Run
//C++ Program Factors of a number
#include <bits/stdc++.h>
using namespace std;

void getFactors(int num){
    
    for(int i = 1; i <= sqrt(num); i++)
    {
        if (num % i == 0){
            
            // Example (10,10) we only want to print once
            // If both factors are equal then print just one
            if(i == num/i)
                cout << i << " ";
            // other wise print both
            else
                cout << i << " " << num/i << " "; 
        }
    }
}

//main Program
int main()
{
    int num =100;
     
    getFactors(num);
}
// Time Complexity: O(√N)
// Space Complexity: O(1)
// Issue : Doesn't print in ascending order

Output

1 100 2 50 4 25 5 20 10

Method 3

This method uses knowledge of vectors.

  • Use the previous general approach
  • Delay printing of larger pair value by not printing it and adding it to a vector
  • Print the vector at the end in reverse order.

Method 3 Code:-

Run 
//C++ Program Factors of a number
#include <bits/stdc++.h>
using namespace std;

void getFactors(int num){
    
    // Vector to store larger pair value
    vector v;
    
    for(int i = 1; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            
            // Example (10,10) we only want to print once
            // If both factors are equal then print just one
            if(i == num/i)
                cout << i << " ";
            // other wise print both
            else
            {
                cout << i << " "; // larger pair pushed, so can be printed later v.push_back(num / i); } } } // print vector in reverse for (int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]); } //main Program int main() { int num; cout << "Enter a positive number: "; cin >> num; getFactors(num); } // Time Complexity: O(√N) // Auxilary Space Complexity: O(√N)

Output

Enter a positive number: 100
1 2 4 5 10 20 25 50 100

Method 4

This method uses another decrementing for loop and doesn’t use any extra space as well.

Method 4 Code:-

Run
//C++ Program Factors of a number
#include<bits/stdc++.h>
using namespace std; 

void getFactors(int num){
    
    // Same i used in other for loop
    int i;
    // to avoid double printing
    int flag = false;
    
    for(i = 1; i <= sqrt(num); i++)
    {
        if (num % i == 0)
            cout << i << " ";
// To avoid double printing of equal pairs
// Example (10,10) we only want to print once
if(i == num/i)
flag = true;
}

// if flag is true then we had double pairs like (10,10)
// we should do i-- so as not to do double printing of pair divisor
// doing i -=2 rather than i-- as in previous for loop we exited
// with i++, example, i = 10 became 11 and we need to start with 9
// so as to ignore 10 as its a double pair
if(flag)
i -= 2;

// printing pairs
for(;i>=1;i--) { if (num % i == 0) cout << num/i << " "; } } //main Program int main() { int num; cout << "Enter a positive number: ";
num=100;
 getFactors(num); 
}
// Time Complexity: O(√N) 
// Space Complexity: O(1)

Output

1 2 4 5 10 20 25 50 100