Trial division algorithm for integer factorization

Here given code implementation process.

import java.util.ArrayList;
// Java program for
// Trial division algorithm for integer factorization
public class Factorization
{
	public void trialDivision(int num)
	{
		if (num <= 1)
		{
			return;
		}
		ArrayList < Integer > ans = new ArrayList < Integer > ();
		int n = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.add(2);
			// Reduce the n by 2
			n = n / 2;
		}
		int f = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.add(f);
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans.add(n);
		}
		System.out.print("\n Given Num    : " + num);
		System.out.print("\n Prime Factor :");
		// Display calculated result
		for (int i = 0; i < ans.size(); ++i)
		{
			System.out.print("  " + ans.get(i));
		}
	}
	public static void main(String[] args)
	{
		Factorization task = new Factorization();
		// Test
		task.trialDivision(1001);
		task.trialDivision(75);
		task.trialDivision(532);
		task.trialDivision(181);
	}
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
// Include header file
#include <iostream>
#include <vector>

using namespace std;
// C++ program for
// Trial division algorithm for integer factorization
class Factorization
{
	public: void trialDivision(int num)
	{
		if (num <= 1)
		{
			return;
		}
		vector < int > ans;
		int n = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.push_back(2);
			// Reduce the n by 2
			n = n / 2;
		}
		int f = 3;
		while ((f *f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.push_back(f);
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans.push_back(n);
		}
		cout << "\n Given Num    : " << num;
		cout << "\n Prime Factor :";
		// Display calculated result
		for (int i = 0; i < ans.size(); ++i)
		{
			cout << "  " << ans.at(i);
		}
	}
};
int main()
{
	Factorization *task = new Factorization();
	// Test
	task->trialDivision(1001);
	task->trialDivision(75);
	task->trialDivision(532);
	task->trialDivision(181);
	return 0;
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Trial division algorithm for integer factorization
public class Factorization
{
	public void trialDivision(int num)
	{
		if (num <= 1)
		{
			return;
		}
		List < int > ans = new List < int > ();
		int n = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.Add(2);
			// Reduce the n by 2
			n = n / 2;
		}
		int f = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.Add(f);
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans.Add(n);
		}
		Console.Write("\n Given Num    : " + num);
		Console.Write("\n Prime Factor :");
		// Display calculated result
		for (int i = 0; i < ans.Count; ++i)
		{
			Console.Write("  " + ans[i]);
		}
	}
	public static void Main(String[] args)
	{
		Factorization task = new Factorization();
		// Test
		task.trialDivision(1001);
		task.trialDivision(75);
		task.trialDivision(532);
		task.trialDivision(181);
	}
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
package main
import "fmt"
// Go program for
// Trial division algorithm for integer factorization
type Factorization struct {}
func getFactorization() * Factorization {
	var me *Factorization = &Factorization {}
	return me
}
func(this Factorization) trialDivision(num int) {
	if num <= 1 {
		return
	}
	var ans = make([]int,0)
	var n int = num
	for (n % 2 == 0) {
		// When Need to add first prime
		ans = append(ans, 2)
		// Reduce the n by 2
		n = n / 2
	}
	var f int = 3
	for ((f * f) <= n) {
		if (n % f) == 0 {
			// Add prime number
			ans = append(ans, f)
			// Reduce the value of n
			n = n / f
		} else {
			f += 2
		}
	}
	if n != 1 {
		// When n is itself prime
		ans = append(ans, n)
	}
	fmt.Print("\n Given Num    : ", num)
	fmt.Print("\n Prime Factor :")
	// Display calculated result
	for i := 0 ; i < len(ans) ; i++ {
		fmt.Print("  ", ans[i])
	}
}
func main() {
	var task * Factorization = getFactorization()
	// Test
	task.trialDivision(1001)
	task.trialDivision(75)
	task.trialDivision(532)
	task.trialDivision(181)
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
<?php
// Php program for
// Trial division algorithm for integer factorization
class Factorization
{
	public	function trialDivision($num)
	{
		if ($num <= 1)
		{
			return;
		}
		$ans = array();
		$n = $num;
		while ($n % 2 == 0)
		{
			// When Need to add first prime
			$ans[] = 2;
			// Reduce the n by 2
			$n = (int)($n / 2);
		}
		$f = 3;
		while (($f * $f) <= $n)
		{
			if (($n % $f) == 0)
			{
				// Add prime number
				$ans[] = $f;
				// Reduce the value of n
				$n = (int)($n / $f);
			}
			else
			{
				$f += 2;
			}
		}
		if ($n != 1)
		{
			// When n is itself prime
			$ans[] = $n;
		}
		echo("\n Given Num    : ".$num);
		echo("\n Prime Factor :");
		// Display calculated result
		for ($i = 0; $i < count($ans); ++$i)
		{
			echo("  ".$ans[$i]);
		}
	}
}

function main()
{
	$task = new Factorization();
	// Test
	$task->trialDivision(1001);
	$task->trialDivision(75);
	$task->trialDivision(532);
	$task->trialDivision(181);
}
main();

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
// Node JS program for
// Trial division algorithm for integer factorization
class Factorization
{
	trialDivision(num)
	{
		if (num <= 1)
		{
			return;
		}
		var ans = [];
		var n = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.push(2);
			// Reduce the n by 2
			n = parseInt(n / 2);
		}
		var f = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.push(f);
				// Reduce the value of n
				n = parseInt(n / f);
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans.push(n);
		}
		process.stdout.write("\n Given Num    : " + num);
		process.stdout.write("\n Prime Factor :");
		// Display calculated result
		for (var i = 0; i < ans.length; ++i)
		{
			process.stdout.write("  " + ans[i]);
		}
	}
}

function main()
{
	var task = new Factorization();
	// Test
	task.trialDivision(1001);
	task.trialDivision(75);
	task.trialDivision(532);
	task.trialDivision(181);
}
main();

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
#  Python 3 program for
#  Trial division algorithm for integer factorization
class Factorization :
	def trialDivision(self, num) :
		if (num <= 1) :
			return
		
		ans = []
		n = num
		while (n % 2 == 0) :
			#  When Need to add first prime
			ans.append(2)
			#  Reduce the n by 2
			n = int(n / 2)
		
		f = 3
		while ((f * f) <= n) :
			if ((n % f) == 0) :
				#  Add prime number
				ans.append(f)
				#  Reduce the value of n
				n = int(n / f)
			else :
				f += 2
			
		
		if (n != 1) :
			#  When n is itself prime
			ans.append(n)
		
		print("\n Given Num    : ", num, end = "")
		print("\n Prime Factor :", end = "")
		i = 0
		#  Display calculated result
		while (i < len(ans)) :
			print("  ", ans[i], end = "")
			i += 1
		
	

def main() :
	task = Factorization()
	#  Test
	task.trialDivision(1001)
	task.trialDivision(75)
	task.trialDivision(532)
	task.trialDivision(181)

if __name__ == "__main__": main()

Output

 Given Num    :  1001
 Prime Factor :   7   11   13
 Given Num    :  75
 Prime Factor :   3   5   5
 Given Num    :  532
 Prime Factor :   2   2   7   19
 Given Num    :  181
 Prime Factor :   181
#  Ruby program for
#  Trial division algorithm for integer factorization
class Factorization 
	def trialDivision(num) 
		if (num <= 1) 
			return
		end

		ans = []
		n = num
		while (n % 2 == 0) 
			#  When Need to add first prime
			ans.push(2)
			#  Reduce the n by 2
			n = n / 2
		end

		f = 3
		while ((f * f) <= n) 
			if ((n % f) == 0) 
				#  Add prime number
				ans.push(f)
				#  Reduce the value of n
				n = n / f
			else
 
				f += 2
			end

		end

		if (n != 1) 
			#  When n is itself prime
			ans.push(n)
		end

		print("\n Given Num    : ", num)
		print("\n Prime Factor :")
		i = 0
		#  Display calculated result
		while (i < ans.length) 
			print("  ", ans[i])
			i += 1
		end

	end

end

def main() 
	task = Factorization.new()
	#  Test
	task.trialDivision(1001)
	task.trialDivision(75)
	task.trialDivision(532)
	task.trialDivision(181)
end

main()

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
import scala.collection.mutable._;
// Scala program for
// Trial division algorithm for integer factorization
class Factorization()
{
	def trialDivision(num: Int): Unit = {
		if (num <= 1)
		{
			return;
		}
		var ans: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		var n: Int = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans += 2;
			// Reduce the n by 2
			n = n / 2;
		}
		var f: Int = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans += f;
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans += n;
		}
		print("\n Given Num    : " + num);
		print("\n Prime Factor :");
		var i: Int = 0;
		// Display calculated result
		while (i < ans.size)
		{
			print("  " + ans(i));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Factorization = new Factorization();
		// Test
		task.trialDivision(1001);
		task.trialDivision(75);
		task.trialDivision(532);
		task.trialDivision(181);
	}
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181
import Foundation;
// Swift 4 program for
// Trial division algorithm for integer factorization
class Factorization
{
	func trialDivision(_ num: Int)
	{
		if (num <= 1)
		{
			return;
		}
		var ans: [Int] = [Int]();
		var n: Int = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.append(2);
			// Reduce the n by 2
			n = n / 2;
		}
		var f: Int = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.append(f);
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n  != 1)
		{
			// When n is itself prime
			ans.append(n);
		}
		print("\n Given Num    : ", num, terminator: "");
		print("\n Prime Factor :", terminator: "");
		var i: Int = 0;
		// Display calculated result
		while (i < ans.count)
		{
			print("  ", ans[i], terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let task: Factorization = Factorization();
	// Test
	task.trialDivision(1001);
	task.trialDivision(75);
	task.trialDivision(532);
	task.trialDivision(181);
}
main();

Output

 Given Num    :  1001
 Prime Factor :   7   11   13
 Given Num    :  75
 Prime Factor :   3   5   5
 Given Num    :  532
 Prime Factor :   2   2   7   19
 Given Num    :  181
 Prime Factor :   181
// Kotlin program for
// Trial division algorithm for integer factorization
class Factorization
{
	fun trialDivision(num: Int): Unit
	{
		if (num <= 1)
		{
			return;
		}
		val ans: MutableList < Int > = mutableListOf < Int > ();
		var n: Int = num;
		while (n % 2 == 0)
		{
			// When Need to add first prime
			ans.add(2);
			// Reduce the n by 2
			n = n / 2;
		}
		var f: Int = 3;
		while ((f * f) <= n)
		{
			if ((n % f) == 0)
			{
				// Add prime number
				ans.add(f);
				// Reduce the value of n
				n = n / f;
			}
			else
			{
				f += 2;
			}
		}
		if (n != 1)
		{
			// When n is itself prime
			ans.add(n);
		}
		print("\n Given Num    : " + num);
		print("\n Prime Factor :");
		var i: Int = 0;
		// Display calculated result
		while (i < ans.size)
		{
			print("  " + ans[i]);
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Factorization = Factorization();
	// Test
	task.trialDivision(1001);
	task.trialDivision(75);
	task.trialDivision(532);
	task.trialDivision(181);
}

Output

 Given Num    : 1001
 Prime Factor :  7  11  13
 Given Num    : 75
 Prime Factor :  3  5  5
 Given Num    : 532
 Prime Factor :  2  2  7  19
 Given Num    : 181
 Prime Factor :  181

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







© 2021, kalkicode.com, All rights reserved