Case Study · CS · Algorithms
The Prime-Finding Races
The idea
My algorithms course (CSE 3500 at UConn) had a solo project with a simple brief: pick an algorithm we never covered in class, explain it, and analyze its running time. Most of the room reached for something fashionable. I reached for something old: a prime-finding method buried in EWD249, the 1969 manuscript that became Dijkstra’s Notes on Structured Programming, where the worked example running through the text is a program that prints a table of the first thousand primes.
Everyone knows the two standard ways to list primes. Trial division interrogates each candidate separately, testing divisors up to its square root. The sieve of Eratosthenes inverts the question: instead of asking “is this number divisible?” it lets each prime announce its own multiples and strike them out in advance. Dijkstra’s method is a third thing, and almost nobody has seen it. It keeps a pool of pending multiples: one entry per prime found so far, holding the smallest multiple of that prime not yet passed. A new candidate is compared against the smallest entry in the pool. If the candidate is below every pending multiple, no prime can divide it, so it is prime, and it enters the pool carrying its square. If it equals the minimum, it is composite, and the matching entries hop forward by their own prime. Primality decided by comparisons and additions alone; there is no division anywhere in the loop, which mattered on hardware where division was the most expensive thing you could ask for. The same idea was later resurrected for the functional-programming world by Melissa O’Neill’s The Genuine Sieve of Eratosthenes (2009), which is where I first found the trail back to EWD249.
The original deliverable was a video presentation plus a Python file with all three algorithms and a timing harness. A video expires; a demo does not. So this project rebuilds the whole comparison for the web: same three algorithms, raced under one operation budget and timed live on whatever machine is reading this page.
The race
| primes up to | trial division | eratosthenes | dijkstra |
|---|---|---|---|
| 60 | 227 ops | 138 ops | 115 ops |
| 120 | 705 ops | 300 ops | 246 ops |
| 300 | 3,032 ops | 815 ops | 666 ops |
With JavaScript enabled this plate races the three algorithms live, one counted operation at a time, each lane drawing its own mechanism: divisors tested, multiples struck, pool markers advancing. The table is the race's result in numbers; all three always agree on the primes, and never on the price.
The fairness rule is the whole design: every tick spends the same number of counted operations in every lane, so being ahead on the strip means being cheaper, not luckier. One operation is one trial division in the first lane, one array visit or one strike in the second, one comparison or one pool advance in the third. The counters are computed by the same code that draws the picture, and the build-time fallback table is computed by the same module again, so the numbers cannot drift apart.
Watching the mechanisms side by side is what the video could never do. Trial division does real work and throws all of it away: nothing it learns about 91 helps it with 93. The sieve is fast precisely because its pen is lazy; by the time it reaches a composite, the crossing-out happened long ago. And Dijkstra’s lane makes visible a thing that is invisible in code: the pool is the sieve’s crossing-out schedule stored as state instead of scattered across an array. It strikes each composite exactly when needed, never earlier, never twice. That thrift shows in the counters, and it surprised me: at these sizes the pool finishes with fewer counted operations than the sieve itself, because Eratosthenes pays a visit to every single number and strikes composites like 12 once for every distinct prime factor. Hold that thought for the benchmark, where the ranking flips back.
The measurement
Predicted · operations counted on paper
| algorithm | N = 1,000 | N = 10,000 | N = 100,000 | per ×10 of N |
|---|---|---|---|---|
| trial division | 19,615 | 651,750 | 20,932,170 | ×33.2 · ×32.1 |
| eratosthenes | 2,957 | 33,070 | 356,807 | ×11.2 · ×10.8 |
| dijkstra | 2,409 | 26,979 | 293,076 | ×11.2 · ×10.9 |
With JavaScript enabled this plate also runs the measurement: all three algorithms timed in your browser at five values of N and plotted on log-log axes, so you can watch the table's growth factors reappear as slopes. The prediction above is the complete argument either way: multiply N by ten and trial division pays about thirty times more, while both sieves pay barely more than ten.
Measured · milliseconds in this browser
Times all fifteen algorithm-and-N pairs right here; the slowest single run is trial division at N = 250,000, around a tenth of a second.
| N | trial division | eratosthenes | dijkstra |
|---|
The separation has clean arithmetic behind it. Trial division in its plain form (no early exit, kept so the lanes stay comparable) spends about tests per candidate, so in total: the growth factor of roughly per decade that the table shows. Both sieves ride on Mertens’ theorem instead: the strikes cost , and is the slowest-growing function you will ever meet in practice, which is why their measured slope sits just above 1. Dijkstra’s pool does the same advances but pays a logarithmic tax per advance for keeping the pool ordered; the operation counter deliberately excludes that bookkeeping, and the benchmark quietly includes it, which is exactly the gap between the two plates.
What the sieve buys with its speed is a commitment: it must know in advance and allocate the whole array before it can say “2”. Dijkstra’s method never looks past the current candidate. It will happily stream primes forever, holding only its pool, which is why the incremental-sieve idea keeps getting rediscovered wherever lazy evaluation lives.
What the rebuild changed
The structural decision in the rebuild is the pool itself. Dijkstra’s thrift depends entirely on finding the smallest pending multiple cheaply: keep the pool in a flat dictionary and scan it for the minimum, and every candidate pays for the entire pool, which quietly turns the elegant idea into something closer to quadratic and benchmarks the data structure rather than the algorithm. The web version keeps the pool in a binary min-heap, so the invariant the method rests on, that the minimum is always at hand, costs a logarithm per advance instead of a scan. An algorithm is only as good as the structure carrying its invariant, and that lesson was worth more than the assignment.
Two notes on what the plates count. The race counts operations in three different currencies (a modulus, an array write, a heap comparison), and those are not equal-priced in hardware; the counter tells the asymptotic story, and the benchmark plate exists to check it against wall-clock time, JIT wobble and all. And the pool admits every prime as soon as it is found, each entry resting at until the candidates catch up. Dijkstra’s own refinement in EWD249 is stingier, keeping only the primes up to in play, and a browser port of that version, pool size instead of , is the natural next step this page stops short of.