Prime factorization using dynamic programming
Here given code implementation process.
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
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