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
a
withb
, andb
witha % b
(remainder whena
is divided byb
). - 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
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 |