wheel factorization
Wheel factorization is a method for screening out composite numbers^{} by arranging numbers around a circle and then striking out those numbers that are obviously composite as indicated by where they fall around the circle.
Wheel factorization is performed thus:

1.
Use another method to find the first $i$ primes. Multiply the first $i$ primes, obtaining the primorial ${p}_{i}\mathrm{\#}$.

2.
Around a circle, write the numbers 1 to ${p}_{i}\mathrm{\#}$.

3.
On a circle larger than the innermost circle, write the ${p}_{i}\mathrm{\#}+1$ to $2{p}_{i}\mathrm{\#}$, lining up 1 with ${p}_{i}\mathrm{\#}+1$ and $2{p}_{i}\mathrm{\#}$.

4.
Make a few more circles, as desired, but always aligning the numbers according to their residues modulo ${p}_{i}\mathrm{\#}$.

5.
Circle the first $i$ primes, and strike out those numbers that are lined up with them in the outer circles.

6.
For each prime ${p}_{j}$ from 2 to ${p}_{i}$, strike out its multiples^{} from $p_{j}{}^{2}$ to ${p}_{i}\mathrm{\#}$, as well as the numbers on the outer circles with the same residue modulo the primorial.
The name is somewhat misleading, as wheel factorization does not completely factor any number, but merely identifies (in the case of the struckout numbers) one of their prime factors^{}. All wheel factorization does is identify which numbers are coprime^{} to the primorial (the numbers that have not been struck out). Of course the prime numbers^{} greater than the primorial will not be struck out, since they must of course by definition be coprime to the the primorial. But as one does more and more circles, more and more composites will pass undetected by this method, as the likelihood increases that their least prime factor is a primer greater than the primorial. Even the innermost circle will always have at least one composite number avoid being struck out, whenever $i>3$, specifically $p_{i+1}{}^{2}$. And there is no practical reason why this algorithm needs to be performed on a circle, other than that it is more visually interesting to humans than a rectangular table. Indeed, with the sieve of Eratosthenes^{}, if one has chosen a row width that is a multiple of a primorial, one can strike out entire columns at once.
Title  wheel factorization 

Canonical name  WheelFactorization 
Date of creation  20130322 18:22:58 
Last modified on  20130322 18:22:58 
Owner  PrimeFan (13766) 
Last modified by  PrimeFan (13766) 
Numerical id  4 
Author  PrimeFan (13766) 
Entry type  Definition 
Classification  msc 11N35 