(In Python): Write a function gcd(a, b) that returns the greatest common divisor
ID: 3810176 • Letter: #
Question
(In Python): Write a function gcd(a, b) that returns the greatest common divisor of the parameters a and b. You can use the Euclidean algorithm, which is based on the fact that gcd(a, b) = gcd(b mod a, a). Say you want to find the gcd of 462 and 1071:
gcd(462, 1071) = gcd(1071 mod 462, 462) = gcd(147, 462)
gcd(147, 462) = gcd(462 mod 147, 147) = gcd(21, 147)
gcd(21, 147) = gcd(147 mod 21, 21) = gcd(0, 21)
gcd(0, 21) = 21, since the gcd of 0 and any positive integer x is just x itself
Hence, gcd(462, 1071) = 21. Note that it’s not necessary to figure out which number is smaller for the algorithm to work:
gcd(1071, 462) = gcd(462 mod 1071, 1071) = gcd(462, 1071)
Then the algorithm would proceed as before.
Explanation / Answer
PROGRAM CODE:
# greater common Divisor
def gcd(a, b):
while b != 0:
(a, b) = (b, a%b)
return a;
print(gcd(21,147));
print(gcd(147, 462));
print(gcd(462, 1071));
OUTPUT:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.