Playing with prime numbers was one of the first things I did when I learned to program. Back in 2001, on a single-core AMD Athlon with 1 GB of RAM, I managed to sieve intervals around 10^18 with a segmented, wheel-based sieve. A lot has happened since then, but one thing hasn’t changed: my passion for these ancient objects, the building blocks of arithmetic, those freaking indomitable numbers.
In recent years I came back to the idea. After several attempts, and thanks to GordonBGood and Kim Walisch, I started focusing on the constraints of the hardware. A year ago I was still building on GordonBGood’s original JavaScript code, and I began thinking about the cache. Then I came across Kim Walisch’s code for the first time: beyond its mathematical ideas, it showed me what cache management really means.
Over one month I built eratostenes, my own toy in an attempt to tame them. After carefully studying every improvement others had already made, I found a few ideas I haven’t seen elsewhere that make it faster still: on the five machines I’ve measured, it ties or beats primesieve, taking up to 23% less time to count the primes up to 10^13, and up to 30% less near the top of the 64-bit range.
Thanks to GordonBGood, whose page-segmented sieves started this journey, and to Kim Walisch: several of eratostenes’ core structures come straight from primesieve, which is also the benchmark I measure against, and every result is checked against his primecount.