Greatest common divisor (gcd) three ways + the Sieve of Eratosthenes

How to read this

gcd race. Each lane is one algorithm. One tick of the player = one basic operation for every algorithm still running: a division with remainder (mod) for Euclid and for consecutive integer checking; a trial division or a factor comparison for the middle-school method. The marker's distance along its track is how much work that algorithm has done; the lane that runs longest sets the track length.

• Euclid: the chain of pairs (m, n) → (n, m mod n). It stops when n becomes 0; the answer is m.
• Consecutive integer checking: every t tried, counting down from min(m, n). Top mark = "does t divide m?", bottom mark = "does t divide n?" (only asked when the top one is ✓).
• Middle-school: the prime factor lists Fm and Fn, then a merge-like walk that multiplies the common factors into g.

Sieve. Numbers are laid out in rows of ten so multiples line up in columns. The steel cell is the current p. Red is the cell being crossed out now; yellow means "this cell was already crossed out" (wasted work); green cells are confirmed primes. The small label under a crossed cell says which p crossed it first.

Try this

1. Race 60, 24. Euclid needs 2 divisions; consecutive integer checking needs 16 (13 values of t, plus 3 extra tests on n). Scrub to the end and check the counters.
2. Race 89, 55. These are consecutive Fibonacci numbers, the slowest possible inputs for Euclid at this size: every quotient is 1. Count the divisions (9) and compare with log base φ of 55.
3. Race 9973, 9967 (two primes). Consecutive integer checking has to walk t all the way down to 1: almost 10,000 divisions. Euclid still needs only a handful.
4. Switch to the sieve with n = 30. Predict which cells p = 3 will cross out that p = 2 already crossed (12, 18, 24, 30), then press play and check the "repeats" counter.
5. Sieve n = 100. Why does the outer loop stop at p = 10? (Any composite ≤ 100 has a factor ≤ √100.)