| Wheel Factorization |
Article Index for Wheel |
Website Links For Wheel |
Information AboutWheel Factorization |
| CATEGORIES ABOUT WHEEL FACTORIZATION | |
| primality tests | |
| SHOPPER'S DELIGHT | |
|
ALGORITHM # Find the first few prime numbers. This can be done quickly using Sieve Of Eratosthenes . # 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 (''x'' + 1)''n'' in another circle around the inner-most circle, such that ''xn'' + 1 is in the same position as (''x'' − 1)''n''7 + 1. # Repeat steps 4 and 5 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. 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 7 13 19 25 7. Sieving 7 13 19 25 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 EXTERNAL LINKS |