Kodeclik Blog
Python program for the greatest common divisor
To compute the greatest common divisor, or gcd, of given numbers in Python we will learn about two ways: to either implement Euclid’s algorithm or to use the gcd() function in the math module of Python.
But before that what is a real-life situation where you will need to find the greatest common divisor? Suppose I have 32 Kit Kats and 24 Snickers that I wish to distribute to a class of students. What is the largest class size so that each student gets the same number of Kit Kats and Snickers and there is no candy left over?
This is a problem of finding the greatest common divisor (GCD) of 32 and 24. We know that 32 is 2x16 and 24 is 2x12 so 2 is a common factor. But is it the greatest? No. The greatest common factor is 8 because 32 is 8x4 and 24 is 8x3 and there is no greater common factor than 32. So if the class has 8 students then each student can get 4 Kit Kats and 3 Snickers and there will not be any candy left over.
The greatest common divisor (GCD) of two numbers is hence the largest number that divides them both evenly. GCD is useful in a range of arithmetic tasks not just the one shown above.
The gcd is also called the highest common factor (HCF) or greatest common factor (GCF). Let us learn about two ways to implement the GCD in Python.
Method 1: Implement Euclid’s algorithm to find gcd in Python
Euclid’s algorithm is a very simple algorithm that can be implemented recursively in Python. The algorithm basically takes two numbers “a” and “b” (assume that “b” is the larger number). It uses the property that the gcd of “a” and “b”, denoted by gcd(a,b) is the same as gcd(a,b-a). In other words, edit the larger number by subtracting the smaller number from it. Why does this work? Let us try it on the above example.
The gcd(24,32) is the same as gcd(24,8) which you can verify is correct. The reason this works is that if there was a gcd for both numbers it would also be the gcd of the difference between the numbers thrown in. We can use this idea to recursively compute the gcd, like so:
gcd(24,32)
= gcd(24,8) % subtracted 24 from 32 to give 8
= gcd(16,8) % subtracted 8 from 24 to give 16
= gcd(8,8) % subtracted 8 from 16 to give 8
= 8We see that this reduces to a much simpler problem which is to find the gcd of 8 and 8, which is obviously 8.
Here is Python code to implement gcd() via Euclid’s algorithm. We call it “mygcd”.
def mygcd(x,y):
if (x==0 or y==0):
return(x+y)
elif (x==1 or y==1):
return(1)
elif (x==y):
return(x)
elif (x>y):
return (mygcd(x-y,y))
else:
return (mygcd(x,y-x))The code above looks more complex because it is testing for a lot of conditions but it is essentially implementing the same logic as above. First, we may not be sure that the second argument will always be the higher one, so we must account for both cases in our recursion. This is what the last two recursive calls do. Then the various base cases account for the situation when one of the numbers is zero (in which case we simply return the other number), when one of the numbers is one (in which case we simply return 1) and when the two numbers are equal (in which case we return the number).
Let us try using the above code:
print(mygcd(24,32))
print(mygcd(24,42))The output is:
8
6Method 2: Use the gcd() function in the Math module
The easier strategy is to import the math module in Python and use the gcd() function in it, like so:
import math as m
print (m.gcd(24,32))
print (m.gcd(24,42))This code produces the same output as before:
8
6If you liked this blogpost about finding the gcd() learn about square roots and how you can work with square roots in Python!
For more Python content, checkout the math.ceil() and math.floor() functions! Also
learn about the math domain error in Python and how to fix it!
Interested in more things Python? Checkout our post on Python queues. Also see our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares. Finally, master the Python print function!
Want to learn Python with us? Sign up for 1:1 or small group classes.
