Posted on by Kalkicode
Code Algorithm

Wheel Factorization Algorithm

The Wheel Factorization Algorithm is a method for finding the prime factors of a number. It is an efficient algorithm that can handle large numbers with many factors. The basic idea of the Wheel Factorization Algorithm is to use a "wheel" to skip over numbers that are known not to be prime, and only test the numbers that have a chance of being prime.

The wheel is a small array of integers that are used to generate a sequence of numbers to test for primality. The size of the wheel depends on the number being factored and the desired level of efficiency. The algorithm starts by initializing the wheel and then generates a sequence of numbers to test. The numbers are tested for divisibility by small primes using trial division, and then subjected to more advanced tests such as the Miller-Rabin primality test.

The Wheel Factorization Algorithm can be very efficient for factoring large numbers with many factors, but it requires careful tuning of the wheel size and other parameters. There are also more advanced variants of the algorithm that use sieving to generate the candidate numbers to test, which can be even more efficient in some cases.

Here given code implementation process.

``````// Java program for
// Wheel Factorization Algorithm
{
public void isPrime(int n)
{
boolean result = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
int[] arr = {
7 , 11 , 13 , 17 , 19 , 23 , 29 , 31
};
// Get the number of element
int k = arr.length;
// Assume given number is prime
result = true;
int limit = (int) Math.sqrt(n);
for (int i = 0; i < limit && result == true; i += 30)
{
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for (int c = 0; c < k &&
arr[c] < limit && result == true; ++c)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
}
}
}
if (result == true)
{
System.out.print("\n Given number " + n + " is prime number");
}
else
{
System.out.print("\n Given number " + n + " is not prime number");
}
}
public static void main(String[] args)
{
// Test
}
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````// Include header file
#include <iostream>
#include <math.h>

using namespace std;
// C++ program for
// Wheel Factorization Algorithm
{
public: void isPrime(int n)
{
bool result = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
int arr[] = {
7 , 11 , 13 , 17 , 19 , 23 , 29 , 31
};
// Get the number of element
int k = sizeof(arr) / sizeof(arr[0]);
// Assume given number is prime
result = true;
int limit = (int) sqrt(n);
for (int i = 0; i < limit && result == true; i += 30)
{
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for (int c = 0; c < k &&
arr[c] < limit && result == true; ++c)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
}
}
}
if (result == true)
{
cout << "\n Given number " << n << " is prime number";
}
else
{
cout << "\n Given number " << n << " is not prime number";
}
}
};
int main()
{
// Test
return 0;
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````// Include namespace system
using System;
// Csharp program for
// Wheel Factorization Algorithm
{
public void isPrime(int n)
{
Boolean result = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 &&
n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
int[] arr = {
7 , 11 , 13 , 17 , 19 , 23 , 29 , 31
};
// Get the number of element
int k = arr.Length;
// Assume given number is prime
result = true;
int limit = (int) Math.Sqrt(n);
for (int i = 0; i < limit && result == true; i += 30)
{
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for (int c = 0; c < k &&
arr[c] < limit && result == true; ++c)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
}
}
}
if (result == true)
{
Console.Write("\n Given number " + n + " is prime number");
}
else
{
Console.Write("\n Given number " + n + " is not prime number");
}
}
public static void Main(String[] args)
{
// Test
}
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````package main
import "math"
import "fmt"
// Go program for
// Wheel Factorization Algorithm
return me
}
var result bool = false
if n == 2 || n == 5 || n == 7 {
result = true
} else if n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0 {
// Few Prime numbers greater than 5 and less than 32
var arr = [] int {
7,
11,
13,
17,
19,
23,
29,
31,
}
// Get the number of element
var k int = len(arr)
// Assume given number is prime
result = true
var limit int = int(math.Sqrt(float64(n)))
for i := 0 ; i < limit && result == true ; i += 30 {
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for c := 0 ;
c < k && arr[c] < limit && result == true ; c++ {
if n % (arr[c] + i) == 0 {
// When n is divisible so it's not prime
result = false
}
}
}
}
if result == true {
fmt.Print("\n Given number ", n, " is prime number")
} else {
fmt.Print("\n Given number ", n, " is not prime number")
}
}
func main() {
// Test
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````<?php
// Php program for
// Wheel Factorization Algorithm
{
public	function isPrime(\$n)
{
\$result = false;
if (\$n == 2 || \$n == 5 || \$n == 7)
{
\$result = true;
}
else if (\$n > 2 && \$n % 2 != 0 &&
\$n % 3 != 0 && \$n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
\$arr = array(7, 11, 13, 17, 19, 23, 29, 31);
// Get the number of element
\$k = count(\$arr);
// Assume given number is prime
\$result = true;
\$limit = (int) sqrt(\$n);
for (\$i = 0; \$i < \$limit && \$result == true; \$i += 30)
{
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for (\$c = 0; \$c < \$k &&
\$arr[\$c] < \$limit && \$result == true; ++\$c)
{
if (\$n % (\$arr[\$c] + \$i) == 0)
{
// When n is divisible so it's not prime
\$result = false;
}
}
}
}
if (\$result == true)
{
echo("\n Given number ".\$n.
" is prime number");
}
else
{
echo("\n Given number ".\$n.
" is not prime number");
}
}
}

function main()
{
// Test
}
main();``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````// Node JS program for
// Wheel Factorization Algorithm
{
isPrime(n)
{
var result = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 &&
n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
var arr = [7, 11, 13, 17, 19, 23, 29, 31];
// Get the number of element
var k = arr.length;
// Assume given number is prime
result = true;
var limit = parseInt(Math.sqrt(n));
for (var i = 0; i < limit && result == true; i += 30)
{
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
for (var c = 0; c < k &&
arr[c] < limit && result == true; ++c)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
}
}
}
if (result == true)
{
process.stdout.write("\n Given number " + n +
" is prime number");
}
else
{
process.stdout.write("\n Given number " + n +
" is not prime number");
}
}
}

function main()
{
// Test
}
main();``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````import math
#  Python 3 program for
#  Wheel Factorization Algorithm
def isPrime(self, n) :
result = False
if (n == 2 or n == 5 or n == 7) :
result = True
elif (n > 2 and n % 2 != 0 and n % 3 != 0 and n % 5 != 0) :
#  Few Prime numbers greater than 5 and less than 32
arr = [7, 11, 13, 17, 19, 23, 29, 31]
#  Get the number of element
k = len(arr)
#  Assume given number is prime
result = True
limit = int(math.sqrt(n))
i = 0
while (i < limit and result == True) :
c = 0
#  Check if i + (prime number between 5 to 32)
#  is divisible by n or not
while (c < k and arr[c] < limit and result == True) :
if (n % (arr[c] + i) == 0) :
#  When n is divisible so it's not prime
result = False

c += 1

i += 30

if (result == True) :
print("\n Given number ", n ,
" is prime number", end = "")
else :
print("\n Given number ", n ,
" is not prime number", end = "")

def main() :
#  Test

if __name__ == "__main__": main()``````

Output

`````` Given number  37  is prime number
Given number  1001  is not prime number
Given number  181  is prime number``````
``````#  Ruby program for
#  Wheel Factorization Algorithm
def isPrime(n)
result = false
if (n == 2 || n == 5 || n == 7)
result = true
elsif (n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
#  Few Prime numbers greater than 5 and less than 32
arr = [7, 11, 13, 17, 19, 23, 29, 31]
#  Get the number of element
k = arr.length
#  Assume given number is prime
result = true
limit = Math.sqrt(n).to_i
i = 0
while (i < limit && result == true)
c = 0
#  Check if i + (prime number between 5 to 32)
#  is divisible by n or not
while (c < k && arr[c] < limit && result == true)
if (n % (arr[c] + i) == 0)
#  When n is divisible so it's not prime
result = false
end

c += 1
end

i += 30
end

end

if (result == true)
print("\n Given number ", n ,
" is prime number")
else

print("\n Given number ", n ,
" is not prime number")
end

end

end

def main()
#  Test
end

main()``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````// Scala program for
// Wheel Factorization Algorithm
{
def isPrime(n: Int): Unit = {
var result: Boolean = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
var arr: Array[Int] = Array(7, 11, 13, 17, 19, 23, 29, 31);
// Get the number of element
var k: Int = arr.length;
// Assume given number is prime
result = true;
var limit: Int = scala.math.sqrt(n).toInt;
var i: Int = 0;
while (i < limit && result == true)
{
var c: Int = 0;
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
while (c < k && arr(c) < limit && result == true)
{
if (n % (arr(c) + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
c += 1;
}
i += 30;
}
}
if (result == true)
{
print("\n Given number " + n + " is prime number");
}
else
{
print("\n Given number " + n + " is not prime number");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Test
}
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````
``````import Foundation;
// Swift 4 program for
// Wheel Factorization Algorithm
{
func isPrime(_ n: Int)
{
var result: Bool = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2  != 0 && n % 3  != 0 && n % 5  != 0)
{
// Few Prime numbers greater than 5 and less than 32
let arr: [Int] = [7, 11, 13, 17, 19, 23, 29, 31];
// Get the number of element
let k: Int = arr.count;
// Assume given number is prime
result = true;
let limit: Int = Int(Double(n).squareRoot());
var i: Int = 0;
while (i < limit && result == true)
{
var c: Int = 0;
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
while (c < k && arr[c] < limit && result == true)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
c += 1;
}
i += 30;
}
}
if (result == true)
{
print("\n Given number ", n ,
" is prime number", terminator: "");
}
else
{
print("\n Given number ", n ,
" is not prime number", terminator: "");
}
}
}
func main()
{
// Test
}
main();``````

Output

`````` Given number  37  is prime number
Given number  1001  is not prime number
Given number  181  is prime number``````
``````// Kotlin program for
// Wheel Factorization Algorithm
{
fun isPrime(n: Int): Unit
{
var result: Boolean = false;
if (n == 2 || n == 5 || n == 7)
{
result = true;
}
else if (n > 2 && n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
{
// Few Prime numbers greater than 5 and less than 32
val arr: Array < Int > = arrayOf(7, 11, 13, 17, 19, 23, 29, 31);
// Get the number of element
val k: Int = arr.count();
// Assume given number is prime
result = true;
val limit: Int = Math.sqrt(n.toDouble()).toInt();
var i: Int = 0;
while (i < limit && result == true)
{
var c: Int = 0;
// Check if i + (prime number between 5 to 32)
// is divisible by n or not
while (c < k && arr[c] < limit && result == true)
{
if (n % (arr[c] + i) == 0)
{
// When n is divisible so it's not prime
result = false;
}
c += 1;
}
i += 30;
}
}
if (result == true)
{
print("\n Given number " + n + " is prime number");
}
else
{
print("\n Given number " + n + " is not prime number");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

Output

`````` Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number``````

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.

Categories
Relative Post