How to find all the factors of a natural number in C ++, Python, and JavaScript

0

A factor is a number that exactly divides a given number; that is, it divides the number without leaving any remainder. Finding the factors of a number using programming can help you consolidate your concepts of loops, conditional statements, and modulo operators.

In this article, you will learn how to find all the factors of a natural number using C ++, Python, and JavaScript.

Statement of the problem

We give you a natural number number, you need to find and print all factors other than number.

Example 1: Let num = 60.

The factors of 60 are: 1 2 3 4 5 6 10 12 15 20 30 60

So 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

The output is therefore 1 2 4 5 10 20 25 50 100.

Example 3: Let num = 85.

The factors of 85 are: 1 5 17 85

The output is therefore 1 5 17 85.

Basic approach to solving the problem

You can find all the distinct factors of a number by following the approach below:

  1. Iterate all numbers from 1 to number.

  2. If the number divides perfectly number, print the number.

Using this approach, the time complexity of the solution would be O (n) and the required auxiliary space would be O (1).

C ++ program to find the 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
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;
}

Production:

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

Python program to find the 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)

Production:

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

Related: How to Find LCM and GCD of Two Numbers in Multiple Languages

JavaScript program to find the 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("
");
}

let num1 = 60;
document.write("Factors of " + num1 + " are: " + "
");
findFactors(num1);
let num2 = 100;
document.write("Factors of " + num2 + " are: " + "
");
findFactors(num2);
let num3 = 85;
document.write("Factors of " + num3 + " are: " + "
");
findFactors(num3);
let num4 = 66;
document.write("Factors of " + num4 + " are: " + "
");
findFactors(num4);
let num5 = 71;
document.write("Factors of " + num5 + " are: " + "
");
findFactors(num5);

Production:

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

Related: Introduction to the Merge Sort Algorithm

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 only need to print the factor once. As in the example above, (8, 8) are two equal factors. You therefore only need to print them once.

So, you can use the following optimized approach to find all the distinct factors of a number:

  1. Iterate all numbers from 1 to the square root of number.

  2. If the number divides perfectly number, this means that the number is a factor of number.

  3. Now check whether the second factor (number/ 1st factor) is equal to the first factor.

  4. If the two factors are equal, print the factor once.

  5. If the two factors are unequal, print both factors.

Using this approach, the time complexity of the solution is O (sqrt (n)) and the required auxiliary space is O (1).

C ++ program using an optimized approach to find the 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
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;
}

Production:

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

Related: How to Reverse a String in C ++, Python, and JavaScript

Python program using an optimized approach to find the 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)

Production:

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

JavaScript program using an optimized approach to find the 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("
");
}

let num1 = 60;
document.write("Factors of " + num1 + " are: " + "
");
findFactors(num1);
let num2 = 100;
document.write("Factors of " + num2 + " are: " + "
");
findFactors(num2);
let num3 = 85;
document.write("Factors of " + num3 + " are: " + "
");
findFactors(num3);
let num4 = 66;
document.write("Factors of " + num4 + " are: " + "
");
findFactors(num4);
let num5 = 71;
document.write("Factors of " + num5 + " are: " + "
");
findFactors(num5);

Production:

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

Understand the basic principles of programming

As a programmer it is very important to understand basic programming principles such as KISS (Keep It Simple, Stupid), DRY (Don’t repeat yourself), Sole Responsibility, YAGNI (You won’t need it) , Open / Closed, Composition on inheritance, etc.

Following the basics of programming will make you a better programmer.


good programmer
10 basic programming principles every programmer should know

Your code should be clear and easy to maintain. Here are several other programming principles to help you clean up your act.

Read more


About the Author


Source link

Share.

About Author

Leave A Reply