Priya R
Updated date Nov 16, 2023
In this blog, we will walk you through the process of finding the Greatest Common Divisor (GCD) in Python using multiple methods. Learn about the Euclidean Algorithm, the math library, and more to efficiently compute the GCD.

## Introduction:

The Greatest Common Divisor (GCD) is a fundamental concept in mathematics, and it finds applications in various fields, from number theory to computer science. In this blog, we will explore different methods to calculate the GCD in Python

## Method 1: The Euclidean Algorithm

The Euclidean Algorithm is one of the most efficient and well-known methods for calculating the GCD of two numbers. It relies on the fact that the GCD of two numbers remains the same if we subtract the smaller number from the larger one repeatedly. Here's a Python program using this method:

``````def gcd_euclidean(a, b):
while b:
a, b = b, a % b
return a

# Example usage
num1 = 48
num2 = 18
result = gcd_euclidean(num1, num2)
print("GCD of", num1, "and", num2, "is", result)
``````

### Output:

``````GCD of 48 and 18 is 6
``````

The Euclidean Algorithm starts by repeatedly subtracting the smaller number from the larger one until one of them becomes zero. In this case, we subtract 18 from 48, which leaves us with 30. We continue this process until we get a remainder of 0, which is the GCD of 48 and 18.

## Method 2: Using Python's math library

Python provides a built-in math library that includes a function to calculate the GCD of two numbers. This method is simple and convenient for those who don't want to implement the algorithm from scratch:

``````import math

num1 = 48
num2 = 18
result = math.gcd(num1, num2)
print("GCD of", num1, "and", num2, "is", result)
``````

### Output:

``````GCD of 48 and 18 is 6
``````

The `math.gcd()` function in Python's math library directly calculates the GCD of the given numbers, making it a straightforward and efficient option for finding the GCD.

## Conclusion:

In this blog, we have explored several methods for calculating the Greatest Common Divisor (GCD) in Python. Whether you prefer using the Euclidean Algorithm for its efficiency, Python's math library for simplicity, or other methods, you have a variety of tools at your disposal to find the GCD of two numbers. Understanding the principles behind these methods is important for both beginners and more advanced programmers.