| Knuth Art Of Computer Programming V1 p2
-----------------------------------------------------------------------
Algorithm E (Euclid's algorithm). Given two positive integers m and n,
find their greatest common divisor, that is, the largest positive integer
that evenly divides both m and n. E1 [Find remained] Divide m by n and r be the remainder. (We will
know that 0 <= r < n) E2 [Is it zero?] If r = 0, the algorithm terminates, n is the answer E3 [Reduce] Set m = n, then n = r, then go back to step E1 -----------------------------------------------------------------------
Knuth Art Of Computer Programming V1 p9 Problem 1.1.4 [4] Using Algorithm E compute the greatest common divisor of 2166 and 6099.
Label each step of the algorithm as it is used. ========================================================================
Claude Sonnet 4.6
======================================================================== Starting with m = 2166, n = 6099:
E1: 2166 ÷ 6099 = 0 remainder 2166 → r = 2166
E2: r ≠ 0, continue
E3: m = 6099, n = 2166 E1: 6099 ÷ 2166 = 2 remainder 1767 → r = 1767
E2: r ≠ 0, continue
E3: m = 2166, n = 1767 E1: 2166 ÷ 1767 = 1 remainder 399 → r = 399
E2: r ≠ 0, continue
E3: m = 1767, n = 399 E1: 1767 ÷ 399 = 4 remainder 171 → r = 171
E2: r ≠ 0, continue
E3: m = 399, n = 171 E1: 399 ÷ 171 = 2 remainder 57 → r = 57
E2: r ≠ 0, continue
E3: m = 171, n = 57 E1: 171 ÷ 57 = 3 remainder 0 → r = 0
E2: r = 0, algorithm terminates
GCD(2166, 6099) = 57 |