Python Program to Find the GCD using Euclidean Algorithm

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest number that can divide two numbers without leaving a remainder.

Example: GCD of 24 and 36 → 12 (because 12 is the largest number that divides both 24 and 36).

In this tutorial, we will learn how to calculate GCD using Euclidean Algorithm in Python. It is one of the most efficient ways for GCD calculation.

Read Also: Write a Python Program to Find HCF (GCD)

What is the Euclidean Algorithm?

The Euclidean Algorithm is based on the simple fact that the GCD of two numbers (a, b) is the same as GCD of (b, a % b), until one of them becomes 0.

✔ Step-by-step process:

1. If b = 0, then GCD(a, b) = a.
2. Otherwise, replace a with b, and b with a % b (remainder when a is divided by b).
3. Repeat the process until b becomes 0.

✔ Example Calculation (GCD of 48 and 18):

GCD(48, 18) → GCD(18, 48 % 18) → GCD(18, 12)  
GCD(18, 12) → GCD(12, 18 % 12) → GCD(12, 6)  
GCD(12, 6) → GCD(6, 12 % 6) → GCD(6, 0)  
Since 6 is the last non-zero remainder, the GCD is 6.

Python Program to Find GCD Using Euclidean Algorithm

Method 1: Using Recursion

def gcd(a, b):
    if b == 0:
        return a  # Base case: when b becomes 0
    return gcd(b, a % b)  # Recursive call with new values

# Taking input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# Finding GCD
result = gcd(num1, num2)
print(f"The GCD of {num1} and {num2} is: {result}")

Output

Enter first number: 48
Enter second number: 18
The GCD of 48 and 18 is

Method 2: Using a While Loop (Iterative Approach)

If you don’t want to use recursion, we can solve it using a simple loop.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b  # Swap values
    return a

# Taking input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# Finding GCD
result = gcd(num1, num2)
print(f"The GCD of {num1} and {num2} is: {result}")

Comparison of Methods