Gregory Friedman The Greg Wide Web on the name →

Case Study · CS · Algorithms

The Prime-Finding Races

2026 · demo

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

Operations each algorithm spends finding all primes up to N, for three values of N in the race's range.
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.

Trial division
Sieve of Eratosthenes
Dijkstra's pool · EWD249

Plate I Three algorithms find every prime up to N under the same operation budget, each lane drawing its real mechanism: trial division walks a divisor bracket up to the candidate; Eratosthenes strikes multiples ahead of its pen; Dijkstra's pool rides below its strip as one marker per prime, each sitting on that prime's next pending multiple, the smallest in ochre. Play runs the race, Step advances one operation everywhere, and the counters keep score. Reduced motion keeps Step and Finish, which jump states instantly.

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

Operation counts for each algorithm at N of one thousand, ten thousand, and one hundred thousand, with the growth factor each tenfold increase of N costs.
algorithm N = 1,000N = 10,000N = 100,000 per ×10 of N
trial division 19,615651,75020,932,170 ×33.2 · ×32.1
eratosthenes 2,95733,070356,807 ×11.2 · ×10.8
dijkstra 2,40926,979293,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.

Plate II Prediction, then measurement. Above, the operation counts computed on paper: each tenfold increase of N costs trial division about thirty times more work, and both sieves about eleven times. Below, on the Run button, the same three implementations timed in this browser at five sizes of N and plotted on log-log axes, where the growth law becomes a slope. N stops at 250,000 so the slowest single run stays around a tenth of a second.

The separation has clean arithmetic behind it. Trial division in its plain form (no early exit, kept so the lanes stay comparable) spends about n\sqrt{n} tests per candidate, so Θ(nn)\Theta(n\sqrt{n}) in total: the growth factor of roughly 101.5≈31.610^{1.5} \approx 31.6 per decade that the table shows. Both sieves ride on Mertens’ theorem instead: the strikes cost ∑p≤nn/p≈nln⁡ln⁡n\sum_{p \le n} n/p \approx n \ln\ln n, and ln⁡ln⁡n\ln\ln n 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 nln⁡ln⁡nn \ln\ln n 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 nn 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 nln⁡ln⁡nn \ln\ln n 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 p2p^2 until the candidates catch up. Dijkstra’s own refinement in EWD249 is stingier, keeping only the primes up to n\sqrt{n} in play, and a browser port of that version, pool size π(n)\pi(\sqrt{n}) instead of π(n)\pi(n), is the natural next step this page stops short of.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.