Using a mod-6 wheel is quite common. ntheory (aka Math::Prime::Util) uses a mod-30 wheel which is nice because their are 8 candidates per block, which packs nicely in a byte. The Sieve of Atkin is a twist on mod-30 (among other things, it's mod-60 which lets it skip 2,3,5). Terje Mathisen wrote a neat little monolithic mod-30 sieve in 1998 you can find on the net. I've seen a mod-2310 sieve but it seems very unwieldy for very little gain. PrimeSieve has 3 sieves for use at different sizes. A mod-30 sieve for small sizes, a mod-210 wheel for medium, and an optimized version of Oliveira e Silva's sieve for large sizes.
Quesada and Van Pelt wrote about a mod-30 sieve in 1996 (they cite Luo's 1989 paper), Sorenson in 1991. He even has a section discussing their agreements and disagreements with Luo's paper as well a Pritchard's earlier paper. Sorenson has a paper on Arxiv from March 2015 that I've been meaning to look at, though I don't think it will change anything (e.g. "The proof is a bit artificial and of theoretical interest only. Coding this in
practice seems daunting."). People are still working on these things.
There is no question that primesieve is fast. It's great stuff, and Kim is a sharp developer who has been working on this for many years. He also has a slightly different target -- at large sizes the TOeS algorithm uses a *lot* of memory. I have tried to keep memory use more constrained. This comes up a lot with tables and precalculation, where I really can't do too much, as most users will probably never even call whatever function I'm optimizing, and I get a lot of feedback about trying to keep the initial size down. primesieve, and its sister project primecount, strive to be *fast* and offer C and C++ APIs.
| [reply] |

Hmm, I had never heard before about Xuedong Luo, nor about "Algorithm3".
But when I was in my first year in technical high school (first university year) in computer science, back in 1989-1990, I was given a homework assignment to implement a prime number algorithm in Pascal (I remember it was in Pascal, but it might have been in Basic or in C, the two other languages we had to work with at the time). My first implementation was just a standard Eratosthenes sieve just using odd numbers both for numbers to be examined and for candidate divisors (with a special case for 2, the only even number that is prime).
In that assignment, I then noticed that the algorithm was getting really slow when getting around the 1,000,000 mark (if I remember correctly the timing, hardware of the time was really not like today, especially with my budget PC then). So I offered at least two possible performance optimizations:
- discarding even numbers and multiples of 3;
- choosing possible divisors only among the primes found so far;
If I remember correctly, I obtained the maximum possible mark for that homework assignment.
But if the real advantage of Algorithm3 is just discarding not only odd numbers but also multiples of 3, then I could almost claim to be a co-discoverer (I am of course just joking, I've never published on that, and I am fairly sure some other people thought about that possibility before). But, still, same idea, same period. And I am almost sure that I still have that assignment paper copy in my archives, with the annotations from my professor at the time (at least I still had it very recently, I don't think I have thrown it away in between).
I might try to post the Pascal abridged source code tomorrow, if I remember.
| [reply] |

| [reply] |

I applaud Xuedong Luo, Laurent_R, and others for taking the sieve of Eratosthenes and creating a faster and more compact algorithm.
| [reply] |

| [reply] |

Comment onRe: The sieve of Xuedong Luo (Algorithm3) for generating prime numbersSelectorDownloadCode