3 ways in Python to calculate GCD or HCF of two numbers

How to calculate HCF or GCD of two numbers in Python:

HCF(Highest common factor) or GCD(greatest common divisor) is the largest positive integer which can divide each of the numbers when at least one of the numbers is not zero.

For example, let’s find the HCF of 9 and 18. The divisors of 9 are 1, 3, 9 and the divisors of 18 are 1, 3, 6, 9. So, the highest common factor or greatest common divisor of 9 and 18 is 9.

We will learn different ways to find the HCF of two numbers in Python in this example.

Method 1: Python program to find the HCF of two numbers by using a for loop:

In this example, we will use a for loop that will run from 1 to the smaller number. On each iteration, it will check if the current value of the loop can divide both the numbers or not. If yes, it will assign that value to a variable that will hold the HCF value once the loop ends.

Let’s write down the program:

def get_hcf(first, second):
    smaller_no = first

    if second < first:
        smaller_no = second

    hcf = 1

    for i in range(2, smaller_no + 1):
        if first % i == 0 and second % i == 0:
            hcf = i

    return hcf


n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))

print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')

Here,

• It takes the numbers as inputs from the user and assigns to the n1 and n2 variables.
• The get_hcf method is used to find the HCF of two numbers. It takes the numbers as its arguments and returns the HCF.
• It assigns the smaller number to the smaller_no variable. The for loop runs from 2 to smaller_no to find the HCF value. The HCF is assigned to the hcf variable.

If you run this program, it will print output as below:

Enter the first number: 13
Enter the second number: 52
HCF of 13 and 52 is: 13

Enter the first number: 12
Enter the second number: 46
HCF of 12 and 46 is: 2

Method 2: Python program to find the HCF of two numbers by using a loop in reverse:

Instead of running a loop from 2 to the number, we can also run the loop in reverse, i.e. starting from the smaller number. Once we found any number, we can skip from the loop as that is the HCF.

This is a better approach than the previous one because it will reduce the number of loop steps.

Below is the complete program:

def get_hcf(first, second):
    i = first

    if second < first:
        i = second

    while (i > 0):
        if first % i == 0 and second % i == 0:
            return i
        i = i - 1


n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))

print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')

It will print similar output. In this program, i holds the smaller number and we are using a while loop instead of a for loop. The while loop will keep running until the value of i is greater than 0. If any value of i can divide both first and second, it will return i i.e. this is the HCF.

Method 3: Python program to find the HCF of two numbers by Euclid’s division algorithm:

Euclid’s division algorithm is an easy way to find the HCF of two numbers. The following steps we have to follow:

• Divide the greater number by the smaller number. Keep the remainder in a separate variable.
• Divide the smaller number by the remainder.
• Repeat the above two steps until the remainder become zero. The smaller number in the division will be the required HCF.

Let’s write down the program:

def get_hcf(first, second):
    while (second):
        first, second = second, first % second
    return first


n1 = int(input("Enter the first number: "))
n2 = int(input("Enter the second number: "))

print(f'HCF of {n1} and {n2} is: {get_hcf(n1, n2)}')

Let’s try to find the HCF of 14 and 76:

• 76/14, remainder is 6.
• 14/6, remainder is 2.
• 6/2, remainder is 0. So, 2 is the HCF.

You might also like:

• Python program to check for Moran numbers
• Python program to check if a number is a perfect number or not
• 3 different Python programs to remove the first character of string
• Python assert statement explanation with examples
• 3 different Python programs to get a string after a substring
• Python example to print the function name as string with __name__ and __qualname__
• Python program to check if a number is a Niven or Harshad number