# Implement the GCD Operation in Python

Vaibhhav Khetarpal Aug 10, 2021 Jul 02, 2021 Python Python Number

The greatest common divisor (GCD), also referred to as the Highest Common Factor (HCF) of two values, is the largest number that divides both the given numbers. The greatest common divisor can be calculated and implemented in Python as well.

This tutorial demonstrates the different methods to implement the code for the greatest common divisor in Python.

## Use Recursion to Implement the Code for the GCD in Python

A function calling itself in the function definition block is known as recursion. Recursion can be used to create a function that calculates the `GCD` of two numbers. This process is very useful in reducing the code’s length and comes in handy to minimize unnecessary function calling.

The following code uses recursion to implement the code for the greatest common divisor in Python.

``````def gcd1(x, y):
if(y==0):
return x
else:
return gcd1(y,x%y)

x = 72
b= 60

print ("The gcd is : ",end="")
print (gcd1(72,60))
``````

The above program gives the following result.

Output:

``````The gcd is : 12
``````

## Use a `for` Loop to Implement the Code for the Greatest Common Divisor in Python

A simple `for` loop and the `if-else` statement can help achieve the same task as the other methods in this article.

The following code uses a `for` loop to implement the code for the greatest common divisor in Python.

``````def gcd2(a, b):

if a > b:
small = b
else:
small = a
for i in range(1, small+1):
if((a % i == 0) and (b % i == 0)):
gcd = i

return gcd
a = 72
b = 60

print ("The gcd is : ",end="")
print (gcd2(72,60))
``````

The code above gives the following result.

Output:

``````The gcd is : 12
``````

## Use the Euclidean Algorithm to Implement the Code for the Greatest Common Divisor in Python

The Euclidean Algorithm is another technique that’s capable of quickly calculating the greatest common divisor of two numbers.

The Euclidean Algorithm is defined on two major facts.

• There is no change in the GCD if a smaller number subtracts a larger number. Therefore, we eventually find out the GCD on continued subtraction of the larger value among the two numbers.
• If we divide the smaller number, instead of subtracting here, the algorithm automatically stops when the remainder `0` is encountered.

The following program below uses the Euclidean Algorithm to implement the code for the greatest common divisor in Python.

``````def gcd3(p, q):

while(q):
p, q = q, p % q

return p

p = 72
q = 60

print ("The gcd is : ",end="")
print (gcd3(72,60))
``````

The code provides the following result.

Output:

``````The gcd is : 12
``````

## Use the `math.gcd()` Function to Calculate the Greatest Common Divisor in Python

Now, instead of making a user-defined function, we can simply use the predefined `math.gcd()` function to compute the GCD of two numbers. The `math` module needs to be imported to the Python code in order to use the `gcd()` function.

The following code uses the `math.gcd()` function to calculate the greatest common divisor in Python.

``````import math
a = math.gcd(72,60)
print(a)
``````

The program above provides the following result.

Output:

``````12
``````

In Python 3.5 and above, the `gcd` function is contained within the `math` module. In the earlier Python versions, the `gcd` function was contained in the `fractions` module. However, as of Python 3.5, it has now been deprecated.

Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.