Posted on by Kalkicode
Code Number

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

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.
3. 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).
4. 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).
5. 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)
{
// Test Case
}
}``````

#### 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()
{
// Test Case
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)
{
// Test Case
}
}``````

#### 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()
{
// Test Case
}
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()
{
// Test Case
}
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() :
#  Test Case

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()
#  Test Case
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
}
}``````

#### 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()
{
// Test Case
}
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
{
// Test Case
}``````

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

1. 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.

2. 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.

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

4. 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.

## Comment

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.

Categories
Relative Post