Program to Find the Greatest Common Divisor (GCD) in Python

Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. For example, the GCD of 36 and 60 is 12.

We will explore three different methods to find the GCD of two numbers using Python programming.

Method 1: Using Euclidean Algorithm

The Euclidean algorithm repeatedly replaces the larger number with its remainder when divided by the smaller number until the remainder becomes zero.

def find_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"GCD of {num1} and {num2} is {find_gcd(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 2: Using Recursion

In this method, we use recursion to apply the Euclidean algorithm.

def find_gcd(a, b):
    if b == 0:
        return a
    return find_gcd(b, a % b)

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"GCD of {num1} and {num2} is {find_gcd(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12

Method 3: Using Iteration

In this method, we iterate from the smaller number down to 1 and find the largest number that divides both inputs.

def find_gcd(a, b):
    gcd = 1
    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print(f"GCD of {num1} and {num2} is {find_gcd(num1, num2)}")
            

Output:

Enter first number: 36
Enter second number: 60
GCD of 36 and 60 is 12