Wheel factorization
Wheel factorization is a method for generating lists of mostly prime numbers from a simple mathematical formula and a much smaller list of the first prime numbers. These lists may then be used in trial division or sieves. Because not all the numbers in these lists are prime, doing so introduces inefficient redundant operations... however, the generators themselves require very little memory compared to keeping a pure list of prime numbers. The small list of initial prime numbers constitute complete parameters for the algorithm to generate the remainder of the list. These generators are referred to as wheels. While each wheel may generate an infinite list of numbers, past a certain point the numbers cease to be mostly prime.
The method may further be applied recursively as a prime number wheel sieve to generate more accurate wheels. Much definitive work on wheel factorization, sieves using wheel factorization, and wheel sieve, was done by Paul Pritchard in formulating a series of different algorithms. To visualize the use of a factorization wheel, one may start by writing the natural numbers around circles as shown in the adjacent diagram. The number of spokes is chosen such that prime numbers will have a tendency to accumulate in a minority of the spokes.
1. Find the first 2 prime numbers: 2 and 3.
2. n = 2 × 3 = 6
3.
4. strike off factors of 2 and 3 which are 4 and 6 as factors of 2; 6 as the only factor of 3 is already stricken:
5. x = 1.
xn + 1 = 1 · 6 + 1 = 7.
(x + 1)n = (1 + 1) · 6 = 12.
Write 7 to 12 with 7 aligned with 1.
6. x = 2.
xn + 1 = 2 · 6 + 1 = 13.
(x + 1)n = (2 + 1) · 6 = 18.
Write 13 to 18.
Repeat for the next few lines.
7 and 8. Sieving
9. Sieving
10. The resulting list contains a non-prime number of 25 which is 52. Use other methods such as a sieve to eliminate it to arrive at
Note that by using exactly the next prime number of 5 wheel cycles and eliminating the multiple(s) of that prime (and only that prime) from the resulting list, we have obtained the base wheel as per step 4 for a factorization wheel with base primes of 2, 3, and 5; this is one wheel in advance of the previous 2/3 factorization wheel. One could then follow the steps to step 10 using the next succeeding prime of 7 cycles and only eliminating the multiples of 7 from the resulting list in step 10 (leaving some "relative" primes in this case and all successive cases - i.e some not true fully qualified primes), to get the next further advanced wheel, recursively repeating the steps as necessary to get successively larger wheels.
...
Wikipedia