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

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
// Reduce the n by 2
n = n / 2;
}
int f = 3;
while ((f * f) <= n)
{
if ((n % f) == 0)
{
// Reduce the value of n
n = n / f;
}
else
{
f += 2;
}
}
if (n != 1)
{
// When n is itself prime
}
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)
{
// Test
}
}``````

#### 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)
{
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()
{
// Test
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
// Reduce the n by 2
n = n / 2;
}
int f = 3;
while ((f * f) <= n)
{
if ((n % f) == 0)
{
// Reduce the value of n
n = n / f;
}
else
{
f += 2;
}
}
if (n != 1)
{
// When n is itself prime
}
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)
{
// Test
}
}``````

#### 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 {
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
}``````

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

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

#### 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)
{
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()
{
// Test
}
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
// Reduce the n by 2
n = n / 2;
}
var f: Int = 3;
while ((f * f) <= n)
{
if ((n % f) == 0)
{
// Reduce the value of n
n = n / f;
}
else
{
f += 2;
}
}
if (n != 1)
{
// When n is itself prime
}
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
{
// Test
}``````

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

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