Greatest common divisor of a given set of numbers is the largest number that divides all of the given numbers completely. In this post, we will understand how to compute the GCD of given numbers in different ways.
Note: When both the input values are 0, the GCD is 0.
A TypeError is raised if one of the inputs is not a number.
1. Using recursion
Recursion is memory consuming and has a lot of overhead because the same result is computed multiple times, but if this is the only option, GCD can be computed as shown below.
Let's see the code,
def gcd_func(a,b):
if(b==0):
return a
else:
return gcd_func(b,a%b)
a = 12
b = 48
print ("The gcd of 12 and 48 is : ",end="")
print (gcd_func(60,48))
Output:
The gcd of 12 and 48 is : 12
2. Using looping
A simple for loop can be used that iterates over the smallest element amongst the given values and 1.
Let's see the code,
def gcd_func(x, y):
# checking for the smaller number
if x > y:
small = y
else:
small = x
# using for loop
for i in range(1, small+1):
if((x % i == 0) and (y % i == 0)):
gcd = i
return gcd
a = 12
b = 48
print ("The gcd of 12 and 48 is : ",end="")
print (gcd_func(60,48))
Output:
The gcd of 12 and 48 is : 12
3. Using the Euclidean algorithm
The Euclidean algorithm is based on the below attributes:
-
When a smaller number is subtracted from a larger number, the GCD of them doesn't change. Hence, if the subtraction is continuous, the GCD of both numbers can be obtained.
-
Instead of using subtraction, if the smaller number is divided, the Euclidean algorithm stops once the remainder comes down to 0.
Let's see the code,
def gcd_func(x, y):
while(y):
x, y = y, x % y
return x
a = 12
b = 48
print ("The gcd of 12 and 48 is : ",end="")
print (gcd_func(60,48))
Output:
The gcd of 12 and 48 is : 12
4. Using math.gcd function
The math library in python has a built-in function called gcd that can be conveniently used to find the GCD of two numbers.
Let's take a code example,
import math
print ("The gcd of 12 and 48 is : ",end="")
print (math.gcd(12,48))
Output:
The gcd of 12 and 48 is : 12
Conclusion:
In this post, we saw different ways of computing the GCD of two numbers in Python. Let us know your thoughts on this post in the comment section below.
You may also like:
