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

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

Use the
math.gcd()
Function to Calculate the Greatest Common Divisor in Python
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 ifelse
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 userdefined 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.