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,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.
··· trial division- - eratosthenes─── dijkstra
Measured running times in milliseconds.
N
trial division
eratosthenes
dijkstra
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.