- Foundation
- About 16 min
- 5 practice questions
The greatest common divisor: a first algorithm and improvements
Write a gcd algorithm straight from the definition using lists of divisors, then improve it step by step and count how much work each version does.
If something looks wrong, please tell us.
By the end of this lesson you can
- Find gcd(m, n) by listing divisors, listing common divisors and taking the last one.
- Explain three improvements that reduce the work, ending with an algorithm that needs no lists.
- Count how many numbers each version examines, and explain why all versions are correct.
The greatest common divisor of two numbers is the largest number that divides both. You may know other ways to find it, such as prime factorisation. Here we build an algorithm straight from the definition, so that its correctness is obvious, and then make it faster.
A first algorithm
- Let divisors-of-m be divisors(m).
- Let divisors-of-n be divisors(n).
- Start with an empty list common-divisors.
- For each number x in divisors-of-m: if x also appears in divisors-of-n, add x to common-divisors.
- Report the rightmost (last) entry of common-divisors as gcd(m, n).
Why the last entry? divisors-of-m is in increasing order, and we go through it in order, so common-divisors is also in increasing order. Its last entry is therefore the largest. The list is never empty, because 1 divides every number.
Worked example 1: gcd(24, 36)
divisors-of-m = divisors(24) = [1, 2, 3, 4, 6, 8, 12, 24].
divisors-of-n = divisors(36) = [1, 2, 3, 4, 6, 9, 12, 18, 36].
Go through the first list: 1, 2, 3, 4 and 6 are in the second list; 8 is not; 12 is; 24 is not.
common-divisors = [1, 2, 3, 4, 6, 12].
Last entry: gcd(24, 36) = 12.
The lists here are an example of a data structure: a way of organising information while an algorithm runs. Keeping the lists in increasing order is what made 'take the last entry' work.
Improving the algorithm
Three improvements
- Two separate scans 1 to m, then 1 to n: m + n checks
- One combined scan Each j from 1 to max(m, n) is tested against both numbers: max(m, n) checks
- Scan only to min(m, n) A common divisor cannot exceed the smaller number; keep j if it divides both
- Drop the list Remember only the latest common divisor found
The last version needs only one number to be remembered. Earlier common divisors are of no use once a larger one is found, so we keep a single value called most-recent-common-divisor:
1. Set most-recent-common-divisor to 1 (1 always divides both).
2. For each k from 2 to min(m, n): if k divides both m and n, set most-recent-common-divisor to k.
3. Report most-recent-common-divisor as gcd(m, n).
gcd without lists: start with 1; for each k from 2 to min(m, n), if k divides both m and n, remember k. The last number remembered is the gcd.
Worked example 2: tracing gcd(8, 20)
| k | Divides 8? | Divides 20? | most-recent-common-divisor |
|---|---|---|---|
| (start) | - | - | 1 |
| 2 | Yes | Yes | 2 |
| 3 | No | No | 2 |
| 4 | Yes | Yes | 4 |
| 5 | No | Yes | 4 |
| 6 | No | No | 4 |
| 7 | No | No | 4 |
| 8 | Yes | No | 4 |
The scan ends with most-recent-common-divisor = 4, so gcd(8, 20) = 4. Check: 8 = 4 × 2 and 20 = 4 × 5, and 2 and 5 share no factor other than 1.
Analysing the algorithms
Correctness: the first algorithm follows the definition of gcd directly, so it is clearly correct. Each improvement changes how much work is done, not what is computed, so every version gives the same, correct answer.
Efficiency: for gcd(375, 825), the first version examines 375 + 825 = 1200 possible divisors; the combined scan examines max(375, 825) = 825; scanning to the minimum examines 375. That is a big saving, but the work still grows with the value of the smaller number. If the smaller number grows from 3 digits to 4 digits, about 10 times as many values must be checked; from 3 digits to 5 digits, about 100 times. Can we do better, the way column addition beat counting? The next two lessons answer yes.
Key takeaways
- First gcd algorithm: list divisors of both numbers, list the common ones, report the last (largest).
- Lists in increasing order are a simple data structure that makes the last entry the largest.
- Improvements: one combined scan, scan only up to min(m, n), then keep just the latest common divisor.
- All versions are correct, but their work still grows with the size of the numbers.
Check your understanding
-
1. Using lists of divisors, what is the list common-divisors for 18 and 27?
- [1, 2, 3, 9]
- [3, 9]
- [1, 3, 6, 9]
- [1, 3, 9]
Show answer
Answer: D. divisors(18) = [1, 2, 3, 6, 9, 18] and divisors(27) = [1, 3, 9, 27]. Going through the first list, 1, 3 and 9 are in the second, so common-divisors = [1, 3, 9], and gcd(18, 27) = 9.
-
2. Why does the first gcd algorithm report the rightmost entry of common-divisors?
- Because the list is in increasing order, so the last entry is the largest
- Because the rightmost entry is always the smaller of m and n
- Because the list has only one entry
- Because the leftmost entry is always 0
Show answer
Answer: A. The divisors are found in increasing order and checked in that order, so common-divisors is increasing too. The last entry is the largest common divisor, which is the gcd. The first entry is always 1.
-
3. For m = 40 and n = 100, the first algorithm examines 140 possible divisors. How many does the version with one combined scan up to max(m, n) examine?
- 40
- 140
- 100
- 60
Show answer
Answer: C. The combined scan tests each j from 1 to max(40, 100) = 100 against both numbers, so it examines 100 values instead of 40 + 100 = 140.
-
4. The list-free algorithm is run for gcd(12, 18). What value does most-recent-common-divisor end with?
- 3
- 6
- 12
- 2
Show answer
Answer: B. k runs from 2 to 12. It is updated at k = 2 (to 2), k = 3 (to 3) and k = 6 (to 6). k = 4, 9 and 12 divide only one of the numbers, so no later update happens. The answer is gcd(12, 18) = 6.
-
5. Why is it enough to check possible common divisors only up to min(m, n)?
- Because the gcd is always 1
- Because larger numbers are never divisors
- Because a common divisor cannot be larger than the smaller of the two numbers
- Because max(m, n) is always prime
Show answer
Answer: C. A divisor of a number is never larger than the number itself. A common divisor must divide the smaller number, so it is at most min(m, n), and checking beyond that is wasted work.
Sign in to keep track of the lessons you finish.