Python Program to Calculate HCF (GCD) by Euclidean Algorithm

This python program calculates Highest Common Factor (HCF) a.k.a. Greatest Common Divisor (GCD) of two numbers using Euclidean Algorithm.

To know more about Euclidean Algorithm to calculate HCF or GCD, see Euclidean Algorithm on Wikipedia.

Also try: Calculate HCF Online

Python Source Code: HCF Using Euclidean Algorithom


# Calculating HCF(GCD) using Euclidean ALgorithm

# Defining function to calculate HCF by Euclidean ALgorithm
def hcf(a,b):
    while b:
        temp = b
        b = a %b
        a = temp
    return a

# Reading numbers from user
first = int(input('Enter first number: '))
second = int(input('Enter second number: '))

# Function call & displaying output HCF (GCD)
print('HCF or GCD of %d and %d is %d' %(first, second, hcf(first, second)))

HCF by Euclidean Method Python Program Output

Enter first number: 12
Enter second number: 18
HCF or GCD of 12 and 18 is 6

This python program can be modified to reduce code size as follows:

Python Source Code: HCF Using Euclidean Algorithom (Reduced Code)


# Calculating HCF(GCD) using Euclidean ALgorithm

# Defining function to find HCF the Using Euclidian algorithm
def hcf(a, b):
   while b:
       a, b = b, a % b
       return a

# Reading numbers from user
first = int(input('Enter first number: '))
second = int(input('Enter second number: '))

# Function call & displaying output HCF (GCD)
print('HCF or GCD of %d and %d is %d' %(first, second, hcf(first, second)))