Comment by mschoenert

This prime generating code has fascinated me for a while.

It was first described by E.W. Dijkstra "Notes on Structured Programming (EWD249), 2nd; 1970; TH Eindhoven". https://www.cs.utexas.edu/~EWD/ewd02xx/EWD249.PDF

And then reformulated by D.E. Knuth "Literate Programming; 1984" http://www.literateprogramming.com/knuthweb.pdf

Both use it to demonstrate their way of deriving and documenting an algorithm.

And then R. Martin used it again in his book "Clean Code; 2008". (Though I'm not 100% certain what he wants to demonstrate with his rather difficult formulation.)

For the sake of this email I am going to call it "Dijkstra's algorithm".

If we look at it from an engineering perspective, then Dijkstra's algorithm is never the best choice (at least not in 2025).

If performance is not the most important aspect, e.g. if we need less than 100000 primes, then the straightforward trial division is just as fast - and soooo much simpler (basically impossible to get wrong). Note that this is different in 2025 than it was in 1970, back then multiplications and divisions were much more expensive so it made sense to minimize them.

If performance is the most important aspect, then the sieve of Eratosthenes is much faster. And you can implement the sieve with a sliding window, which is just as fast (or even a bit faster because of caching) and uses a bounded amount of memory.

Concretely - my implementation of the sliding window sieve of Eratosthenes is about 50 times faster than Dijkstra's algorithm (on the same machine) when generating the first 200 million primes (7.5 sec vs 6 min).

The reformulation - both by Ousterhout and Martin - computes multiples for every new prime found. This will quickly lead to overflow, e.g. the 6543-th prime is 65537, so its square will overflow 32 bit unsigned integers. Dijkstra's formulation on the other hand only computes multiples that are actually used to filter, the multiples are never (much) larger than the candidate.

Note that computing the multiples so eagerly will also make the multiples vector unnecessarily large (wasting memory).

Knuth and Dijkstra both remark that there is a subtle problem with the correctness of the algorithm. When incrementing lastMultiple and then later accessing primes[lastMultiple] und multiples[lastMultiple] it is not obvious that those will already be assigned. In fact they will be, but it is very difficult to prove that. It is a consequence of the fact that for every integer n there is always a prime between n and n*n, which follows from Betrand's theorem, a difficult number-theoretical result.

So if you look at Ousterhout's and Martin's reformulation and think "a yes - now I get the algorithm", then beware: You've missed at least two aspects that are relevant for the algorithm's correctness. ;-)