Wheel Factorization - Procedure

Procedure

1. Find the first few prime numbers. They are known or can be found quickly using Sieve of Eratosthenes.
2. Multiply the prime numbers together to give the result n.
3. Write 1 to n in a circle. This will be the inner-most circle.
4. Taking x to be the number of circles written so far, continue to write xn + 1 to xn + n in another circle around the inner-most circle, such that xn + 1 is in the same position as (x − 1)n + 1.
5. Repeat step 4 until the largest number to be tested for primality.
6. Strike off the number 1.
7. Strike off the spokes of prime numbers (found in step 1) with its multiples without striking off the numbers in the inner-most circles.
8. Strike off the spokes of all multiples of prime numbers found in step 1.
9. The remaining numbers in the wheel contain mostly prime numbers. Use other methods such as Sieve of Eratosthenes to remove the remaining non-primes.