Posted on by Kalkicode
Code Dynamic Programming

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:

  1. Create a boolean array to mark prime numbers up to a certain limit. In this code, the limit is set to 1,000,000.
  2. Calculate the prime numbers using the Sieve of Eratosthenes algorithm. Mark all the multiples of each prime number as non-prime.
  3. Define a function to find the next prime number that is divisible by a given number x.
  4. Initialize the variable p to 2 (the first prime number).
  5. Create an ArrayList to store the prime factors.
  6. 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.
  7. 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  43
package 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  43
import 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  43
import 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  43

The 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 prime array 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 main function, 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.

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.

New Comment