How to Implement the GCD Operation in Python

1. Use Recursion to Implement the Code for the GCD in Python
2. Use a for Loop to Implement the Code for the Greatest Common Divisor in Python
3. Use the Euclidean Algorithm to Implement the Code for the Greatest Common Divisor in Python
4. 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 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.