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.

Python Source Code: HCF Using Euclidean Algorithm

# 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)))