Wheel factorization

From Wikipedia, the free encyclopedia

In number theory, wheel factorization is a type of sieve where numbers are written around circles in a specific manner for the sieve to operate. Prime numbers in the innermost circle have their multiples in similar positions as themselves in the other circles, forming spokes of primes and their multiples. Multiples of the prime numbers in the innermost circle form spokes of all non-prime numbers with the outer circles.

[edit] Algorithm

  1. Find the first few prime numbers. This can be done 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 (x + 1)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 steps 4 and 5 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.

[edit] Example

1. Found the first 2 prime numbers--2 and 3.

2. n = 2 · 3 = 6

3.

 1  2  3  4  5  6

4. x = 1. xn + 1 = 1 · 6 + 1 = 7. (x + 1)n = (1 + 1) · 6 = 12. Write 7 to 12 with 7 aligned with 1.

 1  2  3  4  5  6
 7  8  9 10 11 12

5. 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.

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

6. Sieving

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

7. Sieving

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

8. Resultant list contain a non-prime 25. Use other methods of sieve to arrive at

2 3 5 7 11 13 17 19 23 29

[edit] External links

v • d • e
Number-theoretic algorithms
Primality tests
Sieving algorithms
Integer factorization algorithms
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.