HCF using Euclidean Algorithm in Python

Learn about HCF using Euclidean Algorithm in Python in the below code example. Also, refer to the comments in the code snippet to get a detailed view about what’s actually happening.

HCF using Euclidean Algorithm in Python

We divide the greater by the smaller and take the remainder in this algorithm. Divide the smaller number by the remainder. Repeat until the residual equals zero.

The below program calculates the HCF or GCD od two numbers given by the user.

Program:

# Python program to find GCD of two numbers 

def compute_gcd(x, y): 
    while(y):
        x, y = y, x%y
    return x

# inputs from user
num1 = int(input('First Number: '))
num2 = int(input('Second Number: '))

# function call
print('The GCD of',num1,'and',num2,'is',compute_gcd(num1, num2))

Output:

First Number: 12
Second Number: 36
The GCD of 12 and 36 is 12

Hope above code works for you and Refer the below Related Codes to gain more insights. Happy coding and come back again.