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:
- If
b = 0, thenGCD(a, b) = a. - Otherwise, replace
awithb, andbwitha % b(remainder whenais divided byb). - Repeat the process until
bbecomes 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.
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.
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}")
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}")
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
Enter first number: 48
Enter second number: 18
The GCD of 48 and 18 is
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}")
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}")
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
| Method | Approach | Pros | Cons |
|---|---|---|---|
| Recursion | Uses function calls | Easy to understand | May cause stack overflow for large numbers |
| Iterative (Loop) | Uses a while loop | Efficient & avoids recursion limits | Slightly more code than recursion |
