Python program to find GCD/ HCF of input numbers.

by

Python program to find the GCD (Greatest Common Divisor) of two numbers using three different methods, including the built-in method

Example 1: Using Euclidean Algorithm

The Euclidean Algorithm is a simple and fast way to find the biggest number that can divide two other numbers without leaving a remainder.

Here’s the formula for the Euclidean Algorithm, where a and b are two positive integers, and gcd(a, b) is the greatest common divisor of a and b

Method 1: Using GCD Euclidean Algorithm formula

gcd(a, b) = gcd(b, a mod b)

Implementing Euclidean algorithm in Python to find the GCD of two numbers.

# Using Euclidean Algorithm
def gcd_euclidean(a, b):
    if b == 0:
        return a
    else:
        return gcd_euclidean(b, a % b)

# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))

# Finding GCD using Euclidean Algorithm
gcd = gcd_euclidean(a, b)
print(f"GCD of {a} and {b} using Euclidean Algorithm is: {gcd}")

Output

Enter first number: 12
Enter second number: 103
GCD of 12 and 103 using Euclidean Algorithm is: 1

This above program finds the biggest number that can divide two other numbers without leaving a remainder by repeating a simple calculation until it can’t be done anymore.

Method 2: Using an iterative approach

In this program, we use a Python while loop to find the biggest number that can divide two other numbers without leaving a remainder by repeating a simple calculation until it can’t be done anymore.


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

# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))

# Finding GCD using iterative approach
gcd = gcd_iterative(a, b)
print(f"GCD of {a} and {b} using iterative approach is: {gcd}")

Output

Enter first number: 88
Enter second number: 12
GCD of 88 and 12 using iterative approach is: 4

Method 3: Using built-in function

This program uses a function that already exists in Python to find the biggest number that can divide two other numbers without leaving a remainder.

#  Using built-in function
import math

# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))

# Finding GCD using built-in function
gcd = math.gcd(a, b)
print(f"GCD of {a} and {b} using built-in function is: {gcd}")

Enter first number: 97
Enter second number: 8369
GCD of 97 and 8369 using built-in function is: 1

Conclusion

The above three ways to find the biggest number that can divide two other numbers without leaving a remainder are Euclidean Algorithm, iterative approach, and built-in function. All three methods are easy to use and can help us solve problems in math and programming

Leave a Comment