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:
Start with the number to be factored, n.
Test for divisibility by 2. If n is even, divide it by 2 and add 2 to the factorization list.
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.
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 : 181package 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 : 181import 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 : 181import 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