Write a Python Program to Find HCF or GCD

Finding the highest common factor (HCF) or greatest common divisor (GCD) of two or more numbers is a common problem in mathematics.

In Python, there are several ways to find the HCF/GCD of two or more numbers.

Let’s look at some of these methods.

Using Euclid’s algorithm

Euclid’s algorithm is a well-known method for finding the HCF/GCD of two numbers.

It works by repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is zero.

At this point, the HCF/GCD is the last non-zero remainder.

Here’s the Python code to implement Euclid’s algorithm:

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

In this code, we first define a function called hcf_euclid that takes two arguments a and b.

We then use a while loop to repeatedly divide a by b and take the remainder until b becomes zero.

At this point, we return a, which is the HCF/GCD of the original two numbers.

Python’s built-in math module provides a function called gcd that can be used to find the GCD of two or more numbers.

Here’s the code to use the gcd function:

import math

a = 10
b = 25
c = 50

hcf = math.gcd(math.gcd(a, b), c)

print(hcf)

In this code, we first import the math module.

We then define three variables a, b, and c, and assign them some values.

We then use the gcd function to find the GCD of a and b, and then use the result of that to find the GCD of c and the previous result.

Finally, we print the HCF/GCD.

We can also find the HCF/GCD of two numbers using a recursive function.

Here’s the Python code to implement this method:

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

In this code, we define a function called hcf_recursive that takes two arguments a and b.

If b is zero, we return a, which is the HCF/GCD of the original two numbers.

Otherwise, we call the hcf_recursive function with b and the remainder of a divided by b.

In this tutorial, we have seen three different methods to find the HCF/GCD of two or more numbers in Python.

These methods include using Euclid’s algorithm, the math module, and a recursive function.

Depending on the situation, one method may be more appropriate than another.

By understanding these methods, you can choose the best method for your needs.