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 class PrimeNumber
{
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)
{
PrimeNumber task = new PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}
}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
class PrimeNumber
{
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()
{
PrimeNumber *task = new PrimeNumber();
// Test
task->isPrime(37);
task->isPrime(1001);
task->isPrime(181);
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 class PrimeNumber
{
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)
{
PrimeNumber task = new PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}
}Output
Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime numberpackage main
import "math"
import "fmt"
// Go program for
// Wheel Factorization Algorithm
type PrimeNumber struct {}
func getPrimeNumber() * PrimeNumber {
var me *PrimeNumber = &PrimeNumber {}
return me
}
func(this PrimeNumber) 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
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() {
var task * PrimeNumber = getPrimeNumber()
// Test
task.isPrime(37)
task.isPrime(1001)
task.isPrime(181)
}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
class PrimeNumber
{
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()
{
$task = new PrimeNumber();
// Test
$task->isPrime(37);
$task->isPrime(1001);
$task->isPrime(181);
}
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
class PrimeNumber
{
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()
{
var task = new PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}
main();Output
Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime numberimport math
# Python 3 program for
# Wheel Factorization Algorithm
class PrimeNumber :
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() :
task = PrimeNumber()
# Test
task.isPrime(37)
task.isPrime(1001)
task.isPrime(181)
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
class PrimeNumber
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()
task = PrimeNumber.new()
# Test
task.isPrime(37)
task.isPrime(1001)
task.isPrime(181)
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
class PrimeNumber()
{
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 = {
var task: PrimeNumber = new PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}
}Output
Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime numberimport Foundation;
// Swift 4 program for
// Wheel Factorization Algorithm
class PrimeNumber
{
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()
{
let task: PrimeNumber = PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}
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
class PrimeNumber
{
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
{
val task: PrimeNumber = PrimeNumber();
// Test
task.isPrime(37);
task.isPrime(1001);
task.isPrime(181);
}Output
Given number 37 is prime number
Given number 1001 is not prime number
Given number 181 is prime number
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