Find all prime factors of a number
The given problem is to find all the prime factors of a given number. A prime factor of a number is a prime number that divides the given number without leaving a remainder. In other words, it is a factor that is also a prime number. For example, the prime factors of 12 are 2 and 3, because 2 * 2 * 3 = 12.
To solve this problem, we need to implement a function that takes an integer as input and outputs its prime factors. The function will find all prime factors by dividing the number by smaller prime numbers until the number becomes 1.
Explanation with Example
Let's take the number 136 as an example to understand how the code works. The prime factorization of 136 is:
136 = 2 * 2 * 2 * 17
Pseudocode and Algorithm
function primeFactors(num)
Print "Prime Factors of", num, "is"
i = 2
// Execute loop until (i) is less than or equal to the square root of num
while i <= sqrt(num):
// Inner loop
while num % i == 0:
// When (i) is a prime factor, print it
Print i
// Reduce num by dividing it with the prime factor (i)
num = num / i
// Increment i by 1 if it is currently 2, otherwise increment by 2
if i == 2:
i = i + 1
else:
i = i + 2
// If num is still greater than 2, it is a remaining prime factor
if num > 2:
Print num
end function
// Test cases
primeFactors(136)
primeFactors(760)
primeFactors(22)
primeFactors(23)
The pseudocode for finding all the prime factors of a number can be summarized as follows:
 Start with the smallest prime number, i.e., 2.
 While the number is divisible by the current prime number, print the prime number as a factor and divide the number by the prime number.
 Increment the prime number by 1 if it is currently 2, otherwise, increment it by 2 (to consider only odd numbers, as all even numbers greater than 2 are not prime).
 Repeat steps 2 and 3 until the square root of the number is reached (since the largest possible prime factor of a number will be its square root).
 If the number is still greater than 2, print it as the remaining prime factor.
Code Solution
Here given code implementation process.
// C Program
// Find all prime factors of a number
#include <stdio.h>
#include <math.h>
// Find the prime factors of a given number
void primeFactors(int num)
{
printf("\n Prime Factors of %d is \n", num);
int i = 2;
// Execute loop until when (i) less than of square root of num
while (i <= sqrt(num))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
printf(" %d", i);
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
printf(" %d\n", num);
}
}
int main()
{
// Test Case
primeFactors(136);
primeFactors(760);
primeFactors(22);
primeFactors(23);
return 0;
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
/*
Java Program
Find all prime factors of a number
*/
public class Factorization
{
// Find the prime factors of a given number
public void primeFactors(int num)
{
System.out.print("\n Prime Factors of " + num + " is \n");
int i = 2;
// Execute loop until when (i) less than of square root of num
while (i <= (int) Math.sqrt(num))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
System.out.print(" " + i);
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
System.out.print(" " + num + "\n");
}
}
public static void main(String[] args)
{
Factorization task = new Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
// Include header file
#include <iostream>
#include <math.h>
using namespace std;
/*
C++ Program
Find all prime factors of a number
*/
class Factorization
{
public:
// Find the prime factors of a given number
void primeFactors(int num)
{
cout << "\n Prime Factors of " << num << " is \n";
int i = 2;
// Execute loop until when (i) less than of square root of num
while (i <= (int) sqrt(num))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
cout << " " << i;
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
cout << " " << num << "\n";
}
}
};
int main()
{
Factorization task = Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
return 0;
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
// Include namespace system
using System;
/*
C# Program
Find all prime factors of a number
*/
public class Factorization
{
// Find the prime factors of a given number
public void primeFactors(int num)
{
Console.Write("\n Prime Factors of " + num + " is \n");
int i = 2;
// Execute loop until when (i) less than of square root of num
while (i <= (int) Math.Sqrt(num))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
Console.Write(" " + i);
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
Console.Write(" " + num + "\n");
}
}
public static void Main(String[] args)
{
Factorization task = new Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
<?php
/*
Php Program
Find all prime factors of a number
*/
class Factorization
{
// Find the prime factors of a given number
public function primeFactors($num)
{
echo "\n Prime Factors of ". $num ." is \n";
$i = 2;
// Execute loop until when (i) less than of square root of num
while ($i <= (int) sqrt($num))
{
// Inner loop
while ($num % $i == 0)
{
// When (i) is divisible by num
echo " ". $i;
// Reduce number
$num = intval($num / $i);
}
if ($i == 2)
{
// When (i) is first prime then visit on next prime
$i = $i + 1;
}
else
{
$i = $i + 2;
}
}
if ($num > 2)
{
// When number is greater than 2 then print num
echo " ". $num ."\n";
}
}
}
function main()
{
$task = new Factorization();
// Test Case
$task>primeFactors(136);
$task>primeFactors(760);
$task>primeFactors(22);
$task>primeFactors(23);
}
main();
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
/*
Node Js Program
Find all prime factors of a number
*/
class Factorization
{
// Find the prime factors of a given number
primeFactors(num)
{
process.stdout.write("\n Prime Factors of " + num + " is \n");
var i = 2;
// Execute loop until when (i) less than of square root of num
while (i <= parseInt(Math.sqrt(num)))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
process.stdout.write(" " + i);
// Reduce number
num = parseInt(num / i);
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
process.stdout.write(" " + num + "\n");
}
}
}
function main()
{
var task = new Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
main();
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
import math
# Python 3 Program
# Find all prime factors of a number
class Factorization :
# Find the prime factors of a given number
def primeFactors(self, num) :
print("\n Prime Factors of ", num ," is ")
i = 2
# Execute loop until when (i) less than of square root of num
while (i <= int(math.sqrt(num))) :
# Inner loop
while (num % i == 0) :
# When (i) is divisible by num
print(" ", i, end = "")
# Reduce number
num = int(num / i)
if (i == 2) :
# When (i) is first prime then visit on next prime
i = i + 1
else :
i = i + 2
if (num > 2) :
# When number is greater than 2 then print num
print(" ", num )
def main() :
task = Factorization()
# Test Case
task.primeFactors(136)
task.primeFactors(760)
task.primeFactors(22)
task.primeFactors(23)
if __name__ == "__main__": main()
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
# Ruby Program
# Find all prime factors of a number
class Factorization
# Find the prime factors of a given number
def primeFactors(num)
print("\n Prime Factors of ", num ," is \n")
i = 2
# Execute loop until when (i) less than of square root of num
while (i <= (Math.sqrt(num)).to_i)
# Inner loop
while (num % i == 0)
# When (i) is divisible by num
print(" ", i)
# Reduce number
num = num / i
end
if (i == 2)
# When (i) is first prime then visit on next prime
i = i + 1
else
i = i + 2
end
end
if (num > 2)
# When number is greater than 2 then print num
print(" ", num ,"\n")
end
end
end
def main()
task = Factorization.new()
# Test Case
task.primeFactors(136)
task.primeFactors(760)
task.primeFactors(22)
task.primeFactors(23)
end
main()
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
/*
Scala Program
Find all prime factors of a number
*/
class Factorization
{
// Find the prime factors of a given number
def primeFactors(n: Int): Unit = {
var num = n;
print("\n Prime Factors of " + num + " is \n");
var i: Int = 2;
// Execute loop until when (i) less than of square root of num
while (i <= (Math.sqrt(num)).toInt)
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
print(" " + i);
// Reduce number
num = (num / i).toInt;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
print(" " + num + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Factorization = new Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
import Foundation
/*
Swift 4 Program
Find all prime factors of a number
*/
class Factorization
{
// Find the prime factors of a given number
func primeFactors(_ n: Int)
{
var num = n;
print("\n Prime Factors of ", num, " is ");
var i: Int = 2;
// Execute loop until when (i) less than of square root of num
while (i <= Int(sqrt(Double(num))))
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
print(" ", i, terminator: "");
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
print(" ", num);
}
}
}
func main()
{
let task: Factorization = Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
main();
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
/*
Kotlin Program
Find all prime factors of a number
*/
class Factorization
{
// Find the prime factors of a given number
fun primeFactors(n: Int): Unit
{
var num = n;
print("\n Prime Factors of " + num + " is \n");
var i: Int = 2;
// Execute loop until when (i) less than of square root of num
while (i <= Math.sqrt(num.toDouble()).toInt())
{
// Inner loop
while (num % i == 0)
{
// When (i) is divisible by num
print(" " + i);
// Reduce number
num = num / i;
}
if (i == 2)
{
// When (i) is first prime then visit on next prime
i = i + 1;
}
else
{
i = i + 2;
}
}
if (num > 2)
{
// When number is greater than 2 then print num
print(" " + num + "\n");
}
}
}
fun main(args: Array <String> ): Unit
{
var task: Factorization = Factorization();
// Test Case
task.primeFactors(136);
task.primeFactors(760);
task.primeFactors(22);
task.primeFactors(23);
}
Output
Prime Factors of 136 is
2 2 2 17
Prime Factors of 760 is
2 2 2 5 19
Prime Factors of 22 is
2 11
Prime Factors of 23 is
23
Time Complexity
The time complexity of the given code is approximately O(sqrt(n)), where n is the input number. The outer loop runs until the square root of the number is reached, and the inner loop, in the worst case, runs log(n) times for each value of i. Since the outer loop runs O(sqrt(n)) times, the overall time complexity is O(sqrt(n)).
Resultant Output Explanation
Let's analyze the output of the provided code for the test cases:

primeFactors(136) outputs: Prime Factors of 136 is 2 2 2 17 This output is correct, as the prime factorization of 136 is 2 * 2 * 2 * 17.

primeFactors(760) outputs: Prime Factors of 760 is 2 2 2 5 19 This output is correct, as the prime factorization of 760 is 2 * 2 * 2 * 5 * 19.

primeFactors(22) outputs: Prime Factors of 22 is 2 11 This output is correct, as the prime factorization of 22 is 2 * 11.

primeFactors(23) outputs: Prime Factors of 23 is 23 This output is correct, as 23 is a prime number, and its only prime factor is 23 itself.
Overall, the code correctly finds all the prime factors of the given numbers and displays the results accordingly.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment