C++ Program - Find all factors of a Number
Objective: Write a C++ program to find all distinct factors (divisors) of a given natural number. The divisors of few numbers are given below:
Number: 10 Divisors: 1 2 5 10 Number: 15 Divisors: 1 3 5 15 Number: 100 Divisors: 1 2 4 5 10 20 25 50 100
Method 1: Using iteration
One of the basic approach is to iterate from 1 to n and in each iteration check whether the number divides n. If it divides then print it.
#include <iostream> using namespace std; //function to print all divisors of a number static void printDivisors(int n) { cout<<"Divisors of "<<n<<" are: "; for(int i = 1; i <= n; i++) { if(n%i == 0) cout<<i<<" "; } cout<<"\n"; } int main(){ printDivisors(10); printDivisors(50); printDivisors(100); return 0; }
The above code will give the following output:
Divisors of 10 are: 1 2 5 10 Divisors of 50 are: 1 2 5 10 25 50 Divisors of 100 are: 1 2 4 5 10 20 25 50 100
Method 2: Optimized Code
Instead of checking the divisibility of the given number from 1 to n, it is checked till square root of n. For a factor larger than square root of n, there must the a smaller factor which is already checked in the range of 1 to square root of n.
#include <iostream> #include <cmath> using namespace std; //function to print all divisors of a number static void printDivisors(int n) { cout<<"Divisors of "<<n<<" are: "; //loop from 1 to sqrt(n) for(int i = 1; i <= sqrt(n); i++) { if(n%i == 0) { if(n/i == i) cout<<i<<" "; else cout<<i<<" "<<n/i<<" "; } } cout<<"\n"; } int main(){ printDivisors(10); printDivisors(50); printDivisors(100); return 0; }
The above code will give the following output:
Divisors of 10 are: 1 10 2 5 Divisors of 50 are: 1 50 2 25 5 10 Divisors of 100 are: 1 100 2 50 4 25 5 20 10
Method 3: Optimized Code with sorted result
In the previous method, results are produced in a irregular fashion (printed in pairs - small number and large number). The result can be sorted by storing the larger number and print them later on. Consider the example below:
#include <iostream> #include <cmath> #include <vector> using namespace std; //function to print all divisors of a number static void printDivisors(int n) { cout<<"Divisors of "<<n<<" are: "; //creating a vector to store larger numbers vector<int> vec; //loop from 1 to sqrt(n) for(int i = 1; i <= sqrt(n); i++) { if(n%i == 0) { if(n/i == i) cout<<i<<" "; else { cout<<i<<" "; //storing the large number of a pair vec.push_back(n/i); } } } //printing stored large numbers of pairs for(int i = vec.size() - 1; i >= 0; i--) cout<<vec[i]<<" "; cout<<"\n"; } int main(){ printDivisors(10); printDivisors(50); printDivisors(100); return 0; }
The above code will give the following output:
Divisors of 10 are: 1 2 5 10 Divisors of 50 are: 1 2 5 10 25 50 Divisors of 100 are: 1 2 4 5 10 20 25 50 100
Method 4: Another Optimized Code
To produce the result in sorted order, we can iterate from 1 to square root of n and printing the number which divides n. After that we can iterate back (in reverse order) and printing the quotient of all numbers which divides n.
#include <iostream> #include <cmath> using namespace std; //function to print all divisors of a number static void printDivisors(int n) { cout<<"Divisors of "<<n<<" are: "; //loop from 1 to sqrt(n) int i; for(i = 1; i <= sqrt(n); i++) { if(n%i == 0) cout<<i<<" "; //handing perfect squares if(n/i == i) { i--; break; } } for(; i >= 1; i--) { if(n%i == 0) cout<<n/i<<" "; } cout<<"\n"; } int main(){ printDivisors(10); printDivisors(50); printDivisors(100); return 0; }
The above code will give the following output:
Divisors of 10 are: 1 2 5 10 Divisors of 50 are: 1 2 5 10 25 50 Divisors of 100 are: 1 2 4 5 10 20 25 50 100
Recommended Pages
- C++ Program - To Check Prime Number
- C++ Program - Bubble Sort
- C++ Program - Selection Sort
- C++ Program - Maximum Subarray Sum
- C++ Program - Reverse digits of a given Integer
- C++ Program - Merge Sort
- C++ Program - Shell Sort
- Stack in C++
- Queue in C++
- C++ Program - Find LCM of Two Numbers
- C++ Program - To Check Whether a Number is Palindrome or Not
- C++ Program - To Check Whether a String is Palindrome or Not
- C++ Program - Heap Sort
- C++ Program - Quick Sort
- C++ - Swap Two Numbers without using Temporary Variable
- C++ Program - To Check Armstrong Number
- C++ Program - Counting Sort
- C++ Program - Radix Sort
- C++ Program - Find Largest Number among Three Numbers
- C++ Program - Print Floyd's Triangle