Divisors as a list

To find the gcd (greatest common divisor) straight from its meaning, break the job into pieces we can do:

• list each number's divisors;
• find the numbers in both lists;
• take the largest.

The divisors algorithm:

• start with an empty list;
• for each j = 1, 2, 3, …, n: if j divides n, add j to the end of the list.

Give names to the things you track (list-of-divisors, j). Names make the steps easy to describe, and easy to follow.

Execute it for 18, one j at a time: [ ] → [1] → [1, 2] → [1, 2, 3] → (4, 5 no) → [1, 2, 3, 6] → (7, 8 no) → [1, 2, 3, 6, 9] → (10 to 17 no) → [1, 2, 3, 6, 9, 18].

Because j goes up from 1, the list comes out in increasing order.

How much work? The algorithm checks every number from 1 to n, so its work grows with the size of n: 775 needs about 50 times as many checks as 15.