Finding the Greatest Common Divisor
Write a function that computes the greatest common divisor between x and y. Hint: Use mod. If you want another hint, check out Euclid’s Algorithm.
def gcd(x, y):
"""
>>> gcd(20, 4)
4
>>> gcd(21, 81)
3
"""
"***YOUR CODE HERE***"
def gcd(x, y):
if y == 0:
return x
return gcd(y, x % y)
This problem takes a little bit of math intuition. If you pay close attention, you’ll notice that the mod operator actually helps us find the greatest common divisor. The reason is because when mod returns 0, we’ve successfully found out that those two numbers are divisible by one another. That means that they are in fact divisors. Since we’re taking the modulo each time, we’re getting closer and closer to zero. Any integer mod 1 is zero so we can use that as our base case. When I’ve exhasuted all of the numbers except 1, I know that there won’t be able possible values that are smaller than 1 and are the gcd of any positive number, so I’ve reached my base case.
I don't claim to be perfect so if you find an error on this page, please send me an email preferably with a link to this page so that I know what I need to fix!