Wheel factorization
Encyclopedia
Wheel factorization is a graphical method for manually performing a preliminary to the Sieve of Eratosthenes
that separates prime number
s from composites
. Start by writing the natural numbers around circles as shown below. 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 composite numbers in the outer circles.
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 and 7. Sieving
1 2 3 4 5 6
78 9 10 11 12
1314 15 16 17 18
1920 21 22 23 24
2526 27 28 29 30
8. Sieving
1 2 3 4 5 6
78 9 10 11 12
1314 15 16 17 18
1920 21 22 23 24
2526 27 28 29 30
9. Resultant list contains a non-prime 25. Use other methods of sieve to arrive at
2 3 5 7 11 13 17 19 23 29
(n) / n, which is also the efficiency of the sieve. From the properties of phi, it can easily be seen that the most efficient sieve smaller than x is the one where
and 
. It can also be demonstrated that this efficiency rises very slowly for large n.
To be of maximum use on a computer, we want the numbers that are smaller than n and relatively prime to it as a set. Using a few observations, the set can easily be generated :
Sieve of Eratosthenes
In mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
that separates prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s from composites
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
. Start by writing the natural numbers around circles as shown below. 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 composite numbers in the outer circles.
Procedure
- Find the first few prime numbers. They are known or can be found quickly using Sieve of EratosthenesSieve of EratosthenesIn mathematics, the sieve of Eratosthenes , one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to a specified integer....
. - Multiply the prime numbers together to give the result n.
- Write 1 to n in a circle. This will be the inner-most circle.
- 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.
- Repeat step 4 until the largest number to be tested for primality.
- Strike off the number 1.
- Strike off the spokes of prime numbers (found in step 1) with its multiples without striking off the numbers in the inner-most circles.
- Strike off the spokes of all multiples of prime numbers found in step 1.
- The remaining numbers in the wheel contain mostly prime numbers. Use other methods such as Sieve of Eratosthenes to remove the remaining non-primes.
Example
1. Find 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 and 7. Sieving
7
13
19
25
8. Sieving
7
13
19
25
9. Resultant list contains a non-prime 25. Use other methods of sieve to arrive at
2 3 5 7 11 13 17 19 23 29
Analysis and Computer implementation
Given a number k > n, we know that it is not prime if k mod n and n are not relatively prime. The fraction of numbers that the wheel sieve eliminates is 1 - phiEuler's totient function
In number theory, the totient \varphi of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n In number theory, the totient \varphi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that...
(n) / n, which is also the efficiency of the sieve. From the properties of phi, it can easily be seen that the most efficient sieve smaller than x is the one where
and . It can also be demonstrated that this efficiency rises very slowly for large n.To be of maximum use on a computer, we want the numbers that are smaller than n and relatively prime to it as a set. Using a few observations, the set can easily be generated :
- Start with
, which is the set for 
. - Let
be the set where k has been added to each element of 
. - Then
where 
represents the operation of removing all multiples of x. - 1 and
will be the two smallest of 
when 
removing the need to compute prime numbers separately - The set is symmetrical around
, reducing storage requirements.
External links
- Wheel Factorization
- Improved Incremental Prime Number Sieves by Paul Pritchard