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)
{
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)
{
// Test
}
}

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

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
}

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

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

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

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

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.