# C++ Program to Find the Factors of a Number

## 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 ## 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: 1001 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`