Python Program to Find the GCD of Two Numbers

Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. This tutorial will guide you through creating a Python program that calculates the GCD of two numbers.

Example:

• Input: num1 = 54, num2 = 24

• Output: The GCD of 54 and 24 is 6

• Input: num1 = 8, num2 = 12

• Output: The GCD of 8 and 12 is 4

Problem Statement

Create a Python program that:

• Takes two numbers as input.
• Calculates the GCD of these two numbers.
• Displays the result.

Solution Steps

1. Take Input from the User: Use the input() function to get two numbers from the user.
2. Convert Input to Integer: Convert the input strings to integers using int().
3. Calculate the GCD: Use the Euclidean algorithm to calculate the GCD or utilize Python’s built-in math.gcd() function.
4. Display the Result: Use the print() function to display the GCD.

Python Program Using Euclidean Algorithm

# Python Program to Find the GCD of Two Numbers using Euclidean Algorithm
# Author: https://www.rameshfadatare.com/

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

# Step 2: Define a function to calculate GCD using Euclidean algorithm
def calculate_gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Step 3: Calculate the GCD
gcd = calculate_gcd(num1, num2)

# Step 4: Display the result
print(f"The GCD of {num1} and {num2} is {gcd}")

Python Program Using math.gcd() Function

# Python Program to Find the GCD of Two Numbers using math.gcd()
# Author: https://www.rameshfadatare.com/

import math

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

# Step 2: Calculate the GCD using math.gcd()
gcd = math.gcd(num1, num2)

# Step 3: Display the result
print(f"The GCD of {num1} and {num2} is {gcd}")

Explanation

Euclidean Algorithm:

• Step 1: The program repeatedly replaces the larger number by the remainder of dividing it by the smaller number until the remainder is 0.
• Step 2: The non-zero remainder at this point is the GCD.

Using math.gcd():

• The math.gcd() function from Python’s math module is used to directly compute the GCD of two numbers.

Step 3: Display the Result

• The print() function is used to display the calculated GCD.

Output Example

Example 1:

Enter the first number: 54
Enter the second number: 24
The GCD of 54 and 24 is 6

Example 2:

Enter the first number: 8
Enter the second number: 12
The GCD of 8 and 12 is 4

Conclusion

This Python program demonstrates two methods to find the GCD of two numbers: using the Euclidean algorithm and using Python’s built-in math.gcd() function. This is an important exercise for understanding algorithms, loops, and the use of built-in functions in Python.