Talk:Wheel factorization

I wanted to fix the fact the number 4 was not struck though from step 4 to the end of the algorithm. Upon opening the edit window, I realized that in each of these steps 4 did have the tags. For some reason, these tags are not showing up. Perhaps someone who knows Wikipedia markup better than myself can diagnose what's going wrong. I'm curious to know for future reference.

--Noah

This article is incomprehensible, even with examples, which do not help describe at all what is going on. —Preceding unsigned comment added by 18.202.1.175 (talk) 11:06, 22 April 2009 (UTC)

the linked-to article at http://primes.utm.edu/glossary/page.php?sort=WheelFactorization was able to describe in its first two sentences what this entire article with its examples completely failed at

Where please is the circle in the example? -- Anon.

The formula at the end of step 4 seems wrong. What's the `7' doing there? -- Ralph Corderoy 15:50, 19 November 2006 (UTC)

Fixed. You are right. The "7" was accidentally added when trying to type "&". --68.0.120.35 02:07, 2 March 2007 (UTC)

Shouldn't part 8 of the example be "the non-primes 4 and 25" rather than "a non-prime 25"? 137.219.45.89 06:35, 6 August 2007 (UTC)

The '4' has a strike through - although it's practically invisible on my browser (Firefox, Ubuntu) 144.138.33.93 06:18, 26 September 2007 (UTC)

yup, same on chrome. It's a font issue i suppose Jetru (talk) 14:28, 4 January 2009 (UTC)

"xn + 1 to (x + 1)n" ? Wouldn't it be better to just write "xn + 1 to xn + n" ? -- Anon. —Preceding unsigned comment added by 74.185.249.234 (talk) 20:46, 30 December 2008 (UTC)

Agreed! Shows the range more visibly! Made the changes Jetru (talk) 14:28, 4 January 2009 (UTC)

This is one of the worst maths pages I have ever seen on Wikipedia, managing to make a simple and obvious idea almost incomprehensible. Since anyone likely to be at all interested in this page will almost certainly be going to write a computer program, the talk of writing numbers in circles is entirely unhelpful. All that needs to be said is that a sieve program can automatically eliminate all multiplies of small primes from consideration by considering only numbers prime to the product of the first few small primes. In that case the blindingly obvious thing to do is to consider numbers modulo 30, because there are exactly 8 possible places where primes can occur (30n+1,7,11,13,17,19,23,29), which is perfect for almost any modern computer where bytes have 8 bits. For example you could find and store all the primes apart from 2,3,5 up to 2^16 in a little over 2000 bytes that way. I wrote a C program that used this technique combined with lookup tables which can count all the primes up to 2^64 and reaches 2^32 in a few seconds HugoBarnaby (talk) 16:27, 24 April 2009 (UTC)

Agreed. This article is terrible. "Start by writing the natural numbers around circles as shown below" What? Where? What circle? 12.116.117.150 (talk) 19:57, 19 October 2010 (UTC)

So I was linked to this article from a random page. I agree that it doesn't seam very useful, the "around circles as shown below" when the only circles on the page is when the letter o is used in a word. And while I find math interesting, I haven't gotten to the point where I can find the notation in "Analysis and Computer implementation" comprehensible, it might be, it is just, above me. My question is what is the use of wheel factorization? Is it more efficient than the Sieve of Eratosthenes? Is there a usecase for a prime number sieve that needs a list of known primes to start, and then fails to remove all the composites? Assuming that there is an efficiency advantage over Eratosthenes, how does changing the number of known primes affect that efficiency. I had something else here, but in editing it to save page, figured how to fix the article to make clear the output of the Wheel and how to eliminate the 25 for the desired answer. 174.16.197.160 (talk) 14:32, 5 April 2011 (UTC)

It is in poor shape, explaining a simple concept in a very complex way. It probably should be rewritten from the ground up. CRGreathouse (t | c) 16:17, 5 April 2011 (UTC)

Here is a simple implementation in C++. It prints the efficiency of the wheel. Basically it says that you can eliminate 50% of the numbers by only testing odd numbers for primality. Then you can eliminate a further 17% by not testing numbers that are equal to 3 when you divide by 6. You can eliminate a further 7% (for a total of 73.3%) by only testing numbers that are in a certain list when you divide them by 30. And so on. At the bottom I provide a couple of hints how it can be combined with any other sieve or primality test. -- Nic Roets (talk) 19:34, 5 April 2011 (UTC)

 #include <vector>
 #include <iostream>
 {
   int n = 6, p, i, j, k;
   std::vector<int> s[8]; // Increase this number for a larger wheel.
   s[0].push_back (1);
   s[0].push_back (5);   
   for (i = 1; i < sizeof (s) / sizeof (s[0]); i++) {
     // Now use s[i-1] to generate s[i]
     std::cout << n << " " << 1 - s[i-1].size () / double (n) << '\n';
     p = s[i-1][1];
     for (k = 0; k < p; k++) {
       for (j = 0; j < s[i-1].size (); j++) {
         if ((s[i-1][j] + k * n) % p != 0) s[i].push_back (s[i-1][j] + k * n);
       }
     }
     s[i-1].clear();
     n *= p;
   }  
   //for (j = 0; j < s[i-1].size(); j++) std::cout << s[i-1][j] << ' ';
   // If we want to find all the prime numbers between l*n and l*(n+1), we
   // only need to consider l*n+s[i]. Furthermore, if we use the Sieve of
   // Eratosthenes, we only need to divide by prime numbers larger than p.
 }