Last updated at October 28, 2026 by Teachoo
Transcript
First Algorithm for gcd Combining divisor-finding and list-comparison gives the complete algorithm Algorithm to find gcd(m,n) Algorithm to find gcd(m, n) 1. Let divisors-of-m be the list obtained by computing divisors(m) Let divisors-of-n be the list obtained by computing divisors(n) Start with an empty List common-divisors The World of Algorithms 43 . For each number x in the List of divisors-of-m - If x also appears in the List of divisors-of-n, add x to the List common-divisors . Report the rightmost element of the list common- divisors as gcd(m,n) An important new idea: reuse an existing algorithm We have already written a procedure for finding divisors. We use it twice rather than describe all its steps again. divisors(๐) and divisors(๐) mean "apply the divisor-finding algorithm to these inputs." Why is the complete algorithm correct? The first two steps find every divisor of each input. The comparison step retains exactly the common divisors. Their increasing order is preserved. The last entry is therefore the greatest common divisor. The final step depends on ordering. Choosing the rightmost entry works because the list is increasing-not simply because it is a list.