Last updated at October 28, 2026 by Teachoo
Transcript
Ex 11.3, 1 How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1? Previously, we checked candidates in increasing order: 1, 2, 3,β¦,π Appending each successful candidate produced an increasing divisor list. If we instead check: π,πβπ,πβπ,β¦,π and continue appending successful candidates to the end, the list will be decreasing. Example: Divisors of 18 We examine 18, 17, . . , 1 . The successful candidates appear in this order: 18, 9, 6, 3, 2, 1 Therefore: divisors (ππ)=[18, 9, 6, 3, 2, 1] Similarly: divisors (ππ)=[24, 12, 8, 6, 4, 3, 2, 1] Now examine the divisors of 18 in order and retain those appearing in the list for 24 We examine 18, 17, . . , 1 The successful candidates appear in this order: 18, 9, 6, 3, 2, 1 Therefore: divisors (ππ)=[18, 9, 6, 3, 2, 1] Similarly: divisors (ππ)=[24, 12, 8, 6, 4, 3, 2, 1] Now examine the divisors of 18 in order and retain those appearing in the list for 24 The greatest common divisor is now the leftmost entry. π ππ(ππ,ππ)=π Required change to the original GCD algorithm Replace: Report the rightmost entry of common-divisors. with: Report the leftmost entry of common-divisors. The remaining list-comparison steps can stay the same. If we continued choosing the rightmost entry, we would incorrectly report 1. Divisor of 18 | Also a divisor of 24? | Common-divisor list 18 | No | [] 9 | No | [] 6 | Yes | [6] 3 | Yes | [6, 3] 2 | Yes | [6, 3, 2] 1 | Yes | [6, 3, 2, 1] Report the rightmost entry of common-divisors. with: Report the leftmost entry of common-divisors. The remaining list-comparison steps can stay the same. If we continued choosing the rightmost entry, we would incorrectly report 1.