How would our original algorithm change if we computed the divisors of by examining the numbers from 1 to in reverse order, from down to 1?
The World of Algorithms · Question 9 of 15
How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in…
Examining still finds every divisor, but the list of divisors is now in decreasing order. For 825 it is .
If only divisors-of-n is reversed (divisors-of-m still in increasing order): Step 4 only asks whether each in divisors-of-m appears in divisors-of-n, which does not depend on order. The list common-divisors is built in the order of divisors-of-m, so it is still increasing. For gcd(375, 825) it is , and Step 5 (report the rightmost element) still gives 75. Nothing needs to change.
If we compute every list of divisors in reverse order (so divisors-of-m is reversed too), common-divisors comes out in decreasing order: for gcd(375, 825) it is . Now the gcd is the leftmost element, so Step 5 must change to "Report the leftmost (first) element of the list common-divisors as gcd(m, n)". Reporting the rightmost element would give 1, which is wrong.
This version has a bonus: the first common divisor we find is already the gcd, so in Step 4 we can stop as soon as we find one that appears in divisors-of-n; there is no need to build the whole list.
