Gregory Friedman The Greg Wide Web on the name →

The Prime-Finding Races

Three ways to list the primes

Trial division, the sieve of Eratosthenes, and a third method most people have never seen: Dijkstra's incremental sieve from EWD249, which finds primes without ever dividing. All three come from a CSE 3500 solo project; the story behind them is in the write-up.

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 The race. Three algorithms find every prime up to N under the same operation budget, each lane drawing its real mechanism: trial division walks its divisor bracket up to the candidate; Eratosthenes strikes multiples far ahead of its pen; Dijkstra's pool keeps one pending multiple per prime, drawn as markers under the strip with the smallest in ochre, and decides each candidate by a single comparison. Play runs the race; Step advances one operation everywhere; the counters keep the score.

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 The measurement. The operation counts predicted on paper, then the same three algorithms timed in this browser at five sizes of N and plotted on log-log axes, where a growth law becomes a slope: near 1.5 for trial division, just above 1 for both sieves. N stops at 250,000 so the slowest run stays around a tenth of a second.

Where this algorithm comes from, why it was worth resurrecting, and what the Python original got wrong about its own hero: the case study has the whole story.

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.