Skip to main content

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
Last updated on by Kalkicode




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