Skip to main content

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 number
package 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 number
import 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 number
import 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
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