Skip to main content

Trial division algorithm for integer factorization

Trial division is a basic algorithm for integer factorization. It works by dividing the number to be factored by each potential factor up to the square root of the number.

Here are the steps for the trial division algorithm:

  1. Start with the number to be factored, n.

  2. Test for divisibility by 2. If n is even, divide it by 2 and add 2 to the factorization list.

  3. Test for divisibility by odd numbers greater than 2 up to the square root of n. If a factor is found, divide n by the factor and add the factor to the factorization list. Repeat the test with the new value of n until n is no longer divisible by any prime number.

  4. If n is not equal to 1, it is itself a prime number and should be added to the factorization list.

For example, to factor the number 24, we would start by testing for divisibility by 2, since it is even. We find that 24 is divisible by 2, so we divide by 2 and add 2 to the factorization list:

24 / 2 = 12, factorization list: [2]

Next, we test for divisibility by odd numbers greater than 2 up to the square root of 12 (which is 3.46, so we test for 3):

12 is not divisible by 3, so we move on to the next odd number, which is 5:

12 is not divisible by 5, so we move on to the next odd number, which is 7:

12 is not divisible by 7, so we move on to the next odd number, which is 9 (which is not actually prime, but we still need to test it):

12 is not divisible by 9.

At this point, we have tested all prime numbers up to the square root of 12, so we can conclude that the factorization of 24 is:

24 = 2 * 2 * 2 * 3.

So the prime factors of 24 are 2 and 3, and their multiplicities are 3 and 1, respectively.

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
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