A first gcd algorithm

gcd(375, 825) by lists:

• divisors(375) = [1, 3, 5, 15, 25, 75, 125, 375];
• divisors(825) = [1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825];
• in both: [1, 3, 5, 15, 25, 75];
• so the gcd is 75.

For big numbers, work systematically. With 54000 and 81000 the lists are long. So: for each divisor in the first list, check whether it is in the second; if it is, add it to common-divisors.

1 divides every number, so common-divisors always has at least one entry. The algorithm can never come back empty.

Where is the answer? Both lists are in increasing order, so common-divisors is too, and its rightmost element is the gcd: 27000 for 54000 and 81000.

A list is a data structure: a way of organising the in-between values so an algorithm can use them well.

The same pattern adapts. Keep the elements not in the other list instead; or, for an lcm, test the multiples of one number until the other divides it.