A factor is a number that divides a given number exactly; that is, it divides the number without leaving a remainder. Finding the factors of a number with the help of programming can help you solidify your concepts of loops, conditional statements, and modulo operators.
In this article, you'll learn how to find all factors of a natural number using C++, Python, and JavaScript.
Problem Statement
You're given a natural number num, you need to find and print all the distinct factors of num.
Example 1: Let num = 60.
The factors of 60 are: 1 2 3 4 5 6 10 12 15 20 30 60
Thus the output is 1 2 3 4 5 6 10 12 15 20 30 60.
Example 2: Let num = 100.
The factors of 100 are: 1 2 4 5 10 20 25 50 100
Thus the output is 1 2 4 5 10 20 25 50 100.
Example 3: Let num = 85.
The factors of 85 are: 1 5 17 85
Thus the output is 1 5 17 85.
Basic Approach to Solve the Problem
You can find all distinct factors of a number by following the approach below:
- Iterate all the numbers from 1 to num.
- If the number perfectly divides num, print the number.
Using this approach the time complexity of the solution would be O(n) and the auxiliary space required would be O(1).
C++ Program to Find Factors of a Number
Below is the C++ program to find all the factors of a number:
// C++ program to find all factors of a natural number
#include <iostream>
using namespace std;
void findFactors(int num)
{
for(int i=1; i<=num; i++)
{
if(num%i == 0)
{
cout << i << " ";
}
}
cout << endl;
}
int main()
{
int num1 = 60;
cout << "Factors of " << num1 << " are: " << endl;
findFactors(num1);
int num2 = 100;
cout << "Factors of " << num2 << " are: " << endl;
findFactors(num2);
int num3 = 85;
cout << "Factors of " << num3 << " are: " << endl;
findFactors(num3);
int num4 = 66;
cout << "Factors of " << num4 << " are: " << endl;
findFactors(num4);
int num5 = 71;
cout << "Factors of " << num5 << " are: " << endl;
findFactors(num5);
return 0;
}Output:
Factors of 60 are:
1 2 3 4 5 6 10 12 15 20 30 60
Factors of 100 are:
1 2 4 5 10 20 25 50 100
Factors of 85 are:
1 5 17 85
Factors of 66 are:
1 2 3 6 11 22 33 66
Factors of 71 are:
1 71Python Program to Find Factors of a Number
Below is the Python program to find all the factors of a number:
# Python program to find all factors of a natural number
def findFactors(num):
for i in range(1,num+1):
if (num%i==0):
print(i, end=" ")
print()
num1 = 60
print("Factors of", num1, "are:")
findFactors(num1)
num2 = 100
print("Factors of", num2, "are:")
findFactors(num2)
num3 = 85
print("Factors of", num3, "are:")
findFactors(num3)
num4 = 66
print("Factors of", num4, "are:")
findFactors(num4)
num5 = 71
print("Factors of", num5, "are:")
findFactors(num5)
Output:
Factors of 60 are:
1 2 3 4 5 6 10 12 15 20 30 60
Factors of 100 are:
1 2 4 5 10 20 25 50 100
Factors of 85 are:
1 5 17 85
Factors of 66 are:
1 2 3 6 11 22 33 66
Factors of 71 are:
1 71
JavaScript Program to Find Factors of a Number
Below is the JavaScript program to find all the factors of a number:
// JavaScript program to find all factors of a natural number
function findFactors(num) {
for(let i=1; i<=num; i++) {
if(num%i == 0) {
document.write(i + " ");
}
}
document.write("<br>");
}
let num1 = 60;
document.write("Factors of " + num1 + " are: " + "<br>");
findFactors(num1);
let num2 = 100;
document.write("Factors of " + num2 + " are: " + "<br>");
findFactors(num2);
let num3 = 85;
document.write("Factors of " + num3 + " are: " + "<br>");
findFactors(num3);
let num4 = 66;
document.write("Factors of " + num4 + " are: " + "<br>");
findFactors(num4);
let num5 = 71;
document.write("Factors of " + num5 + " are: " + "<br>");
findFactors(num5);Output:
Factors of 60 are:
1 2 3 4 5 6 10 12 15 20 30 60
Factors of 100 are:
1 2 4 5 10 20 25 50 100
Factors of 85 are:
1 5 17 85
Factors of 66 are:
1 2 3 6 11 22 33 66
Factors of 71 are:
1 71
Optimized Approach to Solve the Problem
If you look at the factors of a number, they appear in pairs. For example if num = 64, the factors of 64 would be: (1, 64), (2, 32), (4, 16), and (8, 8). You can use this fact to optimize your solution.
However, in the case of two equal factors, you need to print the factor only once. Like in the above example, (8, 8) are two equal factors. So you need to print them only once.
Thus, you can use the following optimized approach to find all distinct factors of a number:
- Iterate all the numbers from 1 to square root of num.
- If the number perfectly divides num, it means that the number is a factor of num.
- Now check if the second factor (num/1st factor) is equal to the first factor.
- If both the factors are equal, print the factor once.
- If both factors are unequal, print both factors.
Using this approach the time complexity of the solution is O(sqrt(n)) and the auxiliary space required is O(1).
C++ Program Using Optimized Approach to Find Factors of a Number
Below is the C++ program to find all the factors of a number:
// C++ program to find all factors of a natural number
#include <bits/stdc++.h>
using namespace std;
void findFactors(int num)
{
for(int i=1; i<=sqrt(num); i++)
{
if(num%i == 0)
{
if(num/i == i)
{
cout << i << " ";
}
else
{
cout << i << " " << num/i << " ";
}
}
}
cout << endl;
}
int main()
{
int num1 = 60;
cout << "Factors of " << num1 << " are: " << endl;
findFactors(num1);
int num2 = 100;
cout << "Factors of " << num2 << " are: " << endl;
findFactors(num2);
int num3 = 85;
cout << "Factors of " << num3 << " are: " << endl;
findFactors(num3);
int num4 = 66;
cout << "Factors of " << num4 << " are: " << endl;
findFactors(num4);
int num5 = 71;
cout << "Factors of " << num5 << " are: " << endl;
findFactors(num5);
return 0;
}Output:
Factors of 60 are:
1 60 2 30 3 20 4 15 5 12 6 10
Factors of 100 are:
1 100 2 50 4 25 5 20 10
Factors of 85 are:
1 85 5 17
Factors of 66 are:
1 66 2 33 3 22 6 11
Factors of 71 are:
1 71
Python Program Using Optimized Approach to Find Factors of a Number
Below is the Python program to find all the factors of a number:
# Python program to find all factors of a natural number
import math
def findFactors(num):
i = 1
while i <= math.sqrt(num):
if (num%i==0):
if (num/i == i):
print(i, end=" ")
else:
print(i, num//i, end=" ")
i = i + 1
print()
num1 = 60
print("Factors of", num1, "are:")
findFactors(num1)
num2 = 100
print("Factors of", num2, "are:")
findFactors(num2)
num3 = 85
print("Factors of", num3, "are:")
findFactors(num3)
num4 = 66
print("Factors of", num4, "are:")
findFactors(num4)
num5 = 71
print("Factors of", num5, "are:")
findFactors(num5)
Output:
Factors of 60 are:
1 60 2 30 3 20 4 15 5 12 6 10
Factors of 100 are:
1 100 2 50 4 25 5 20 10
Factors of 85 are:
1 85 5 17
Factors of 66 are:
1 66 2 33 3 22 6 11
Factors of 71 are:
1 71JavaScript Program Using Optimized Approach to Find Factors of a Number
Below is the JavaScript program to find all the factors of a number:
// JavaScript program to find all factors of a natural number
function findFactors(num) {
for(let i=1; i<=Math.sqrt(num); i++) {
if(num%i == 0) {
if (parseInt(num/i, 10) == i)
{
document.write(i + " ");
} else {
document.write(i + " " + parseInt(num/i, 10) + " ");
}
}
}
document.write("<br>");
}
let num1 = 60;
document.write("Factors of " + num1 + " are: " + "<br>");
findFactors(num1);
let num2 = 100;
document.write("Factors of " + num2 + " are: " + "<br>");
findFactors(num2);
let num3 = 85;
document.write("Factors of " + num3 + " are: " + "<br>");
findFactors(num3);
let num4 = 66;
document.write("Factors of " + num4 + " are: " + "<br>");
findFactors(num4);
let num5 = 71;
document.write("Factors of " + num5 + " are: " + "<br>");
findFactors(num5);Output:
Factors of 60 are:
1 60 2 30 3 20 4 15 5 12 6 10
Factors of 100 are:
1 100 2 50 4 25 5 20 10
Factors of 85 are:
1 85 5 17
Factors of 66 are:
1 66 2 33 3 22 6 11
Factors of 71 are:
1 71Understand Basic Programming Principles
As a programmer, it's very important to understand basic programming principles like KISS (Keep It Simple, Stupid), DRY (Don't Repeat Yourself), Single Responsibility, YAGNI (You Aren't Going to Need It), Open/Closed, Composition Over Inheritance, etc.
Following the basic programming principles will ultimately make you a better programmer.
0 Comments