brainwagon

As some of you may have noticed, I occasionally like to write small programs to compute odd little mathematical curiousities. Something I hadn’t done in a long while was to use the Sieve of Eratosthenes to compute a bunch of prime numbers. I suspect that I wrote such a program very early in my exploration of computers, maybe thirty years ago. The basic algorithm is pretty straightforward, but takes O(N) space to find the primes less than N. It’s not hard to reduce the storage to N bits, and with a trivial bit of work you can reduce it to N/2 bits, and with a little more, you can reduce it to 4/15 N bits. That was fun to work out.

But last night I did something a bit different: I implemented a simple “segmented sieve”. Basically, the idea is that to generate all the primes up to N, you find all the primes up to sqrt(N), and save those. Then, you process the rest of the numbers in buffers of sqrt(N) at a time, by sieving each buffer with your saved primes. It’s a really simple idea, but makes sieving larger numbers more practical. I implemented the simplest possible version of this last night, and set it going to compute all the prime numbers up to 1E12. Here’s the log from the run:

[chessboard] % time ./bigsieve 1000000000000 > output
20580.222u 18.741s 5:43:39.10 99.9%     0+0k 0+0io 0pf+0w

And here’s the output file:

78498 primes less than 1000000
148933 primes less than 2000000
216816 primes less than 3000000
283146 primes less than 4000000
348513 primes less than 5000000
412849 primes less than 6000000
476648 primes less than 7000000
539777 primes less than 8000000
602489 primes less than 9000000
664579 primes less than 10000000
...999989 lines deleted...
37607912018 primes less than 1000000000000

The program doesn’t include any of the basic optimizations, I suspect it woudn’t be difficult to make this thing a factor of 2-4 faster without adding a ton of code. I’ll probably see if I can do that over the next few days. It’s a useless but fun project.