Prime factorization using dynamic programming
In this article, we will discuss prime factorization using dynamic programming. We will explain the problem statement, the algorithm used, and provide a solution with the time complexity of the code.
Introduction
Prime factorization is the process of finding the prime numbers that divide a given number exactly. It is an important concept in number theory and has various applications in fields such as cryptography, prime factorization-based algorithms, and prime factorization-based problems.
Problem Statement
The problem is to find the prime factors of a given number. Given an integer num, we need to calculate its prime factors and display the result.
Algorithm
The algorithm for prime factorization using dynamic programming can be summarized as follows:
- Create a boolean array to mark prime numbers up to a certain limit. In this code, the limit is set to 1,000,000.
- Calculate the prime numbers using the Sieve of Eratosthenes algorithm. Mark all the multiples of each prime number as non-prime.
- Define a function to find the next prime number that is divisible by a given number x.
- Initialize the variable p to 2 (the first prime number).
- Create an ArrayList to store the prime factors.
- While the number temp is greater than 1:
- If temp is divisible by p, add p to the list of factors and update temp by dividing it by p.
- Otherwise, find the next prime number greater than p that divides temp and update p accordingly.
- Display the prime factors stored in the ArrayList.
Solution
import java.util.ArrayList;
// Java program for
// Prime factorization using dynamic programming
public class Factorization
{
public int limit;
public boolean[] prime;
public Factorization()
{
// This is prime number limit
this.limit = 1000000;
this.prime = new boolean[this.limit];
this.calculatePrime();
}
// Pre calculate prime number under limit
public void calculatePrime()
{
// Set initial all element is prime
for (int i = 2; i < this.limit; ++i)
{
this.prime[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 * i; j < this.limit; j += i)
{
prime[j] = false;
}
}
}
}
// return a next prime number which is divisible by x
public int nextPrime(int p, int x)
{
for (int i = p + 1; i < this.limit && i <= x; ++i)
{
if (((x % i) == 0) && this.prime[i] == true)
{
return i;
}
}
// Exceed the limit of prime factors
return 1;
}
public void primeFactors(int num)
{
if (num <= 0)
{
return;
}
if (num == 1)
{
System.out.print("1 is neither a prime number ");
System.out.print("nor a composite number");
return;
}
int temp = num;
// First prime element
int p = 2;
// This are used to collect prime factors
ArrayList < Integer > factor = new ArrayList < Integer > ();
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.add(p);
temp = temp / p;
}
else
{
// When need to next prime number
p = nextPrime(p, temp);
if (p == 1)
{
System.out.print(" Factor are outside the range\n");
return;
}
}
}
System.out.print("\n Prime factor of number : " + num + "\n");
// Display calculated result
for (int i = 0; i < factor.size(); ++i)
{
System.out.print(" " + factor.get(i));
}
}
public static void main(String[] args)
{
Factorization task = new Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43// Include header file
#include <iostream>
#include <vector>
using namespace std;
// C++ program for
// Prime factorization using dynamic programming
class Factorization
{
public:
int limit;
bool *prime;
Factorization()
{
this->limit = 1000000;
this->prime = new bool[this->limit];
this->calculatePrime();
}
// Pre calculate prime number under limit
void calculatePrime()
{
// Set initial all element is prime
for (int i = 2; i < this->limit; ++i)
{
this->prime[i] = true;
}
for (int i = 2; i < this->limit; ++i)
{
if (this->prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 *i; j < this->limit; j += i)
{
this->prime[j] = false;
}
}
}
}
// return a next prime number which is divisible by x
int nextPrime(int p, int x)
{
for (int i = p + 1; i < this->limit && i <= x; ++i)
{
if (((x % i) == 0) && this->prime[i] == true)
{
return i;
}
}
// Exceed the limit of prime factors
return 1;
}
void primeFactors(int num)
{
if (num <= 0)
{
return;
}
if (num == 1)
{
cout << "1 is neither a prime number ";
cout << "nor a composite number";
return;
}
int temp = num;
// First prime element
int p = 2;
// This are used to collect prime factors
vector < int > factor;
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.push_back(p);
temp = temp / p;
}
else
{
// When need to next prime number
p = this->nextPrime(p, temp);
if (p == 1)
{
cout << " Factor are outside the range\n";
return;
}
}
}
cout << "\n Prime factor of number : " << num << "\n";
// Display calculated result
for (int i = 0; i < factor.size(); ++i)
{
cout << " " << factor.at(i);
}
}
};
int main()
{
Factorization *task = new Factorization();
// Test
task->primeFactors(642);
task->primeFactors(55);
task->primeFactors(45);
task->primeFactors(731);
task->primeFactors(733236);
return 0;
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Prime factorization using dynamic programming
public class Factorization
{
public int limit;
public Boolean[] prime;
public Factorization()
{
// This is prime number limit
this.limit = 1000000;
this.prime = new Boolean[this.limit];
this.calculatePrime();
}
// Pre calculate prime number under limit
public void calculatePrime()
{
// Set initial all element is prime
for (int i = 2; i < this.limit; ++i)
{
this.prime[i] = true;
}
for (int i = 2; i < this.limit; ++i)
{
if (this.prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (int j = 2 * i; j < this.limit; j += i)
{
this.prime[j] = false;
}
}
}
}
// return a next prime number which is divisible by x
public int nextPrime(int p, int x)
{
for (int i = p + 1; i < this.limit && i <= x; ++i)
{
if (((x % i) == 0) && this.prime[i] == true)
{
return i;
}
}
// Exceed the limit of prime factors
return 1;
}
public void primeFactors(int num)
{
if (num <= 0)
{
return;
}
if (num == 1)
{
Console.Write("1 is neither a prime number ");
Console.Write("nor a composite number");
return;
}
int temp = num;
// First prime element
int p = 2;
// This are used to collect prime factors
List < int > factor = new List < int > ();
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.Add(p);
temp = temp / p;
}
else
{
// When need to next prime number
p = this.nextPrime(p, temp);
if (p == 1)
{
Console.Write(" Factor are outside the range\n");
return;
}
}
}
Console.Write("\n Prime factor of number : " + num + "\n");
// Display calculated result
for (int i = 0; i < factor.Count; ++i)
{
Console.Write(" " + factor[i]);
}
}
public static void Main(String[] args)
{
Factorization task = new Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43package main
import "fmt"
// Go program for
// Prime factorization using dynamic programming
type Factorization struct {
limit int
prime []bool
}
func getFactorization() * Factorization {
var me *Factorization = &Factorization {}
// This is prime number limit
me.limit = 1000000
me.prime = make([] bool, me.limit)
// Set initial all element is prime
for i := 0; i < me.limit; i++ {
me.prime[i] = true
}
me.prime[0] = false
me.prime[1] = false
me.calculatePrime()
return me
}
// Pre calculate prime number under limit
func(this Factorization) calculatePrime() {
for i := 2 ; i < this.limit ; i++ {
if this.prime[i] == true {
// Inactive the multiple prime value of [i]
for j := 2 * i ; j < this.limit ; j += i {
this.prime[j] = false
}
}
}
}
// return a next prime number which is divisible by x
func(this Factorization) nextPrime(p, x int) int {
for i := p + 1 ; i < this.limit && i <= x ; i++ {
if ((x % i) == 0) && this.prime[i] == true {
return i
}
}
// Exceed the limit of prime factors
return 1
}
func(this Factorization) primeFactors(num int) {
if num <= 0 {
return
}
if num == 1 {
fmt.Print("1 is neither a prime number ")
fmt.Print("nor a composite number")
return
}
var temp int = num
// First prime element
var p int = 2
// This are used to collect prime factors
var factor []int
for (temp > 1) {
if (temp % p) == 0 {
factor = append(factor, p)
temp = temp / p
} else {
// When need to next prime number
p = this.nextPrime(p, temp)
if p == 1 {
fmt.Print(" Factor are outside the range\n")
return
}
}
}
fmt.Print("\n Prime factor of number : ", num, "\n")
// Display calculated result
for i := 0 ; i < len(factor) ; i++ {
fmt.Print(" ", factor[i])
}
}
func main() {
var task * Factorization = getFactorization()
// Test
task.primeFactors(642)
task.primeFactors(55)
task.primeFactors(45)
task.primeFactors(731)
task.primeFactors(733236)
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43<?php
// Php program for
// Prime factorization using dynamic programming
class Factorization
{
public $limit;
public $prime;
public function __construct()
{
$this->limit = 100000;
// Set initial all element is prime
$this->prime = array_fill(0, $this->limit, true);
$this->prime[0] = false;
$this->prime[1] = false;
$this->calculatePrime();
}
// Pre calculate prime number under limit
public function calculatePrime()
{
for ($i = 2; $i < $this->limit; ++$i)
{
if ($this->prime[$i] == true)
{
// Inactive the multiple prime value of [i]
for ($j = 2 * $i; $j < $this->limit; $j += $i)
{
$this->prime[$j] = false;
}
}
}
}
// return a next prime number which is divisible by x
public function nextPrime($p, $x)
{
for ($i = $p + 1; $i < $this->limit && $i <= $x; ++$i)
{
if ((($x % $i) == 0) && $this->prime[$i] == true)
{
return $i;
}
}
// Exceed the limit of prime factors
return 1;
}
public function primeFactors($num)
{
if ($num <= 0)
{
return;
}
if ($num == 1)
{
echo("1 is neither a prime number ");
echo("nor a composite number");
return;
}
$temp = $num;
// First prime element
$p = 2;
// This are used to collect prime factors
$factor = array();
while ($temp > 1)
{
if (($temp % $p) == 0)
{
$factor[] = $p;
$temp = (int)($temp / $p);
}
else
{
// When need to next prime number
$p = $this->nextPrime($p, $temp);
if ($p == 1)
{
echo(" Factor are outside the range\n");
return;
}
}
}
echo("\n Prime factor of number : ".$num."\n");
// Display calculated result
for ($i = 0; $i < count($factor); ++$i)
{
echo(" ".$factor[$i]);
}
}
}
function main()
{
$task = new Factorization();
// Test
$task->primeFactors(642);
$task->primeFactors(55);
$task->primeFactors(45);
$task->primeFactors(731);
$task->primeFactors(733236);
}
main();Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43// Node JS program for
// Prime factorization using dynamic programming
class Factorization
{
constructor()
{
this.limit = 1000000;
this.prime = Array(this.limit).fill(true);
this.prime[0] = false;
this.prime[1] = false;
this.calculatePrime();
}
// Pre calculate prime number under limit
calculatePrime()
{
for (var i = 2; i < this.limit; ++i)
{
if (this.prime[i] == true)
{
// Inactive the multiple prime value of [i]
for (var j = 2 * i; j < this.limit; j += i)
{
this.prime[j] = false;
}
}
}
}
// return a next prime number which is divisible by x
nextPrime(p, x)
{
for (var i = p + 1; i < this.limit && i <= x; ++i)
{
if (((x % i) == 0) && this.prime[i] == true)
{
return i;
}
}
// Exceed the limit of prime factors
return 1;
}
primeFactors(num)
{
if (num <= 0)
{
return;
}
if (num == 1)
{
process.stdout.write("1 is neither a prime number ");
process.stdout.write("nor a composite number");
return;
}
var temp = num;
// First prime element
var p = 2;
// This are used to collect prime factors
var factor = [];
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.push(p);
temp = parseInt(temp / p);
}
else
{
// When need to next prime number
p = this.nextPrime(p, temp);
if (p == 1)
{
process.stdout.write(" Factor are outside the range\n");
return;
}
}
}
process.stdout.write("\n Prime factor of number : " + num + "\n");
// Display calculated result
for (var i = 0; i < factor.length; ++i)
{
process.stdout.write(" " + factor[i]);
}
}
}
function main()
{
var task = new Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}
main();Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43# Python 3 program for
# Prime factorization using dynamic programming
class Factorization :
def __init__(self) :
self.limit = 1000000
self.prime = [True] * (self.limit)
self.prime[0] = False
self.prime[1] = False
self.calculatePrime()
# Pre calculate prime number under limit
def calculatePrime(self) :
i = 2
while (i < self.limit) :
if (self.prime[i] == True) :
j = 2 * i
# Inactive the multiple prime value of [i]
while (j < self.limit) :
self.prime[j] = False
j += i
i += 1
# return a next prime number which is divisible by x
def nextPrime(self, p, x) :
i = p + 1
while (i < self.limit and i <= x) :
if (((x % i) == 0) and self.prime[i] == True) :
return i
i += 1
# Exceed the limit of prime factors
return 1
def primeFactors(self, num) :
if (num <= 0) :
return
if (num == 1) :
print("1 is neither a prime number ", end = "")
print("nor a composite number", end = "")
return
temp = num
# First prime element
p = 2
# This are used to collect prime factors
factor = []
while (temp > 1) :
if ((temp % p) == 0) :
factor.append(p)
temp = int(temp / p)
else :
# When need to next prime number
p = self.nextPrime(p, temp)
if (p == 1) :
print(" Factor are outside the range")
return
print("\n Prime factor of number : ", num )
i = 0
# Display calculated result
while (i < len(factor)) :
print(" ", factor[i], end = "")
i += 1
def main() :
task = Factorization()
# Test
task.primeFactors(642)
task.primeFactors(55)
task.primeFactors(45)
task.primeFactors(731)
task.primeFactors(733236)
if __name__ == "__main__": main()Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43# Ruby program for
# Prime factorization using dynamic programming
class Factorization
# Define the accessor and reader of class Factorization
attr_reader :limit, :prime
attr_accessor :limit, :prime
Array.new() {false}
def initialize()
self.limit = 1000000
self.prime = Array.new(self.limit) {true}
self.prime[0] = false
self.prime[1] = false
self.calculatePrime()
end
# Pre calculate prime number under limit
def calculatePrime()
i = 2
while (i < self.limit)
if (self.prime[i] == true)
j = 2 * i
# Inactive the multiple prime value of [i]
while (j < self.limit)
self.prime[j] = false
j += i
end
end
i += 1
end
end
# return a next prime number which is divisible by x
def nextPrime(p, x)
i = p + 1
while (i < self.limit && i <= x)
if (((x % i) == 0) && self.prime[i] == true)
return i
end
i += 1
end
# Exceed the limit of prime factors
return 1
end
def primeFactors(num)
if (num <= 0)
return
end
if (num == 1)
print("1 is neither a prime number ")
print("nor a composite number")
return
end
temp = num
# First prime element
p = 2
# This are used to collect prime factors
factor = []
while (temp > 1)
if ((temp % p) == 0)
factor.push(p)
temp = temp / p
else
# When need to next prime number
p = self.nextPrime(p, temp)
if (p == 1)
print(" Factor are outside the range\n")
return
end
end
end
print("\n Prime factor of number : ", num ,"\n")
i = 0
# Display calculated result
while (i < factor.length)
print(" ", factor[i])
i += 1
end
end
end
def main()
task = Factorization.new()
# Test
task.primeFactors(642)
task.primeFactors(55)
task.primeFactors(45)
task.primeFactors(731)
task.primeFactors(733236)
end
main()Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43import scala.collection.mutable._;
// Scala program for
// Prime factorization using dynamic programming
class Factorization(var limit: Int,
var prime: Array[Boolean])
{
def this()
{
this(1000000, Array.fill[Boolean](1000000)(true));
this.prime(0) = false;
this.prime(1) = false;
this.calculatePrime();
}
// Pre calculate prime number under limit
def calculatePrime(): Unit = {
var i: Int = 2;
while (i < this.limit)
{
if (prime(i) == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < this.limit)
{
prime(j) = false;
j += i;
}
}
i += 1;
}
}
// return a next prime number which is divisible by x
def nextPrime(p: Int, x: Int): Int = {
var i: Int = p + 1;
while (i < this.limit && i <= x)
{
if (((x % i) == 0) && this.prime(i) == true)
{
return i;
}
i += 1;
}
// Exceed the limit of prime factors
return 1;
}
def primeFactors(num: Int): Unit = {
if (num <= 0)
{
return;
}
if (num == 1)
{
print("1 is neither a prime number ");
print("nor a composite number");
return;
}
var temp: Int = num;
// First prime element
var p: Int = 2;
// This are used to collect prime factors
var factor: ArrayBuffer[Int] = new ArrayBuffer[Int]();
while (temp > 1)
{
if ((temp % p) == 0)
{
factor += p;
temp = temp / p;
}
else
{
// When need to next prime number
p = nextPrime(p, temp);
if (p == 1)
{
print(" Factor are outside the range\n");
return;
}
}
}
print("\n Prime factor of number : " + num + "\n");
var i: Int = 0;
// Display calculated result
while (i < factor.size)
{
print(" " + factor(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Factorization = new Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43import Foundation;
// Swift 4 program for
// Prime factorization using dynamic programming
class Factorization
{
var limit: Int;
var prime: [Bool];
init()
{
self.limit = 1000000;
self.prime = Array(repeating: true, count: self.limit);
self.prime[0] = false;
self.prime[1] = false;
self.calculatePrime();
}
// Pre calculate prime number under limit
func calculatePrime()
{
var i: Int = 2;
while (i < self.limit)
{
if (self.prime[i] == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < self.limit)
{
self.prime[j] = false;
j += i;
}
}
i += 1;
}
}
// return a next prime number which is divisible by x
func nextPrime(_ p: Int, _ x: Int) -> Int
{
var i: Int = p + 1;
while (i < self.limit && i <= x)
{
if (((x % i) == 0) && self.prime[i] == true)
{
return i;
}
i += 1;
}
// Exceed the limit of prime factors
return 1;
}
func primeFactors(_ num: Int)
{
if (num <= 0)
{
return;
}
if (num == 1)
{
print("1 is neither a prime number ", terminator: "");
print("nor a composite number", terminator: "");
return;
}
var temp: Int = num;
// First prime element
var p: Int = 2;
// This are used to collect prime factors
var factor: [Int] = [Int]();
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.append(p);
temp = temp / p;
}
else
{
// When need to next prime number
p = self.nextPrime(p, temp);
if (p == 1)
{
print(" Factor are outside the range");
return;
}
}
}
print("\n Prime factor of number : ", num );
var i: Int = 0;
// Display calculated result
while (i < factor.count)
{
print(" ", factor[i], terminator: "");
i += 1;
}
}
}
func main()
{
let task: Factorization = Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}
main();Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43// Kotlin program for
// Prime factorization using dynamic programming
class Factorization
{
var limit: Int;
var prime: Array < Boolean > ;
constructor()
{
this.limit = 1000000;
this.prime = Array(this.limit)
{
true
};
this.prime[0] = false;
this.prime[1] = false;
this.calculatePrime();
}
// Pre calculate prime number under limit
fun calculatePrime(): Unit
{
var i: Int = 2;
while (i < this.limit)
{
if (this.prime[i] == true)
{
var j: Int = 2 * i;
// Inactive the multiple prime value of [i]
while (j < this.limit)
{
this.prime[j] = false;
j += i;
}
}
i += 1;
}
}
// return a next prime number which is divisible by x
fun nextPrime(p: Int, x: Int): Int
{
var i: Int = p + 1;
while (i < this.limit && i <= x)
{
if (((x % i) == 0) && this.prime[i] == true)
{
return i;
}
i += 1;
}
// Exceed the limit of prime factors
return 1;
}
fun primeFactors(num: Int): Unit
{
if (num <= 0)
{
return;
}
if (num == 1)
{
print("1 is neither a prime number ");
print("nor a composite number");
return;
}
var temp: Int = num;
// First prime element
var p: Int = 2;
// This are used to collect prime factors
val factor: MutableList < Int > = mutableListOf < Int > ();
while (temp > 1)
{
if ((temp % p) == 0)
{
factor.add(p);
temp = temp / p;
}
else
{
// When need to next prime number
p = this.nextPrime(p, temp);
if (p == 1)
{
print(" Factor are outside the range\n");
return;
}
}
}
print("\n Prime factor of number : " + num + "\n");
var i: Int = 0;
// Display calculated result
while (i < factor.size)
{
print(" " + factor[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Factorization = Factorization();
// Test
task.primeFactors(642);
task.primeFactors(55);
task.primeFactors(45);
task.primeFactors(731);
task.primeFactors(733236);
}Output
Prime factor of number : 642
2 3 107
Prime factor of number : 55
5 11
Prime factor of number : 45
3 3 5
Prime factor of number : 731
17 43
Prime factor of number : 733236
2 2 3 7 7 29 43The above code implements the prime factorization using dynamic programming. It initializes an instance of the Factorization class, which calculates prime numbers up to the given limit using the Sieve of Eratosthenes algorithm. The primeFactors function takes a number as input and finds its prime factors using the previously calculated prime numbers. The prime factors are stored in an ArrayList and displayed as the output.
The code has been tested with sample inputs, and the output for each input is displayed below the function calls:
Prime factors of number: 642 2 3 107 Prime factors of number: 55 5 11 Prime factors of number: 45 3 3 5 Prime factors of number: 731 17 43 Prime factors of number: 733236 2 2 3 7 7 29 43
Time Complexity
The time complexity of the prime factorization algorithm using dynamic programming can be analyzed as follows:
- The initialization of the
primearray takes O(n) time and space, where n is the limit of prime numbers to be calculated (in this case, 1,000,000). - The calculation of prime numbers using the Sieve of Eratosthenes algorithm takes O(nlog(log(n))) time.
- The prime factorization of a number takes O(sqrt(num)) time in the worst case, as we iterate up to the square root of the given number to find its factors.
- Since we are performing prime factorization for multiple numbers in the
mainfunction, the overall time complexity of the program can be approximated as O(N * sqrt(M)), where N is the number of inputs and M is the maximum value among the inputs.
In this article, we explored the concept of prime factorization using dynamic programming. We discussed the problem statement, presented an algorithm for prime factorization, and provided a solution implemented in Java. The code calculates prime numbers using the Sieve of Eratosthenes algorithm and finds the prime factors of given numbers. We also analyzed the time complexity of the algorithm. Prime factorization is a fundamental concept in number theory, and understanding it can be beneficial when dealing with various mathematical and computational problems.
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