Python Program to Find HCF or GCD

HCF stands for Highest Common Factor, also known as Greatest Common Divisor (GCD). It is the largest positive integer that divides two or more integers without leaving a remainder. For example, the factors of 12 are 1, 2, 3, 4, 6, and 12.

Python Code : #

The below Python program finds the highest common factor (HCF) or greatest common divisor (GCD) of two numbers:

# take input from user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))

# determine the smaller number
if num1 < num2:
    smaller = num1
else:
    smaller = num2

# iterate from 1 to the smaller number and check for factors
hcf = 1
for i in range(1, smaller+1):
    if num1 % i == 0 and num2 % i == 0:
        hcf = i

# print the HCF
print("The HCF of", num1, "and", num2, "is", hcf)

In this program, we first take input from the user for the two numbers whose HCF/GCD is to be found. We then determine the smaller of the two numbers using an if statement.

We then use a for loop to iterate from 1 to the smaller number, checking for factors of both numbers using the modulus operator (%). If a common factor is found, we store it in the variable hcf.

Finally, we print the HCF/GCD of the two numbers using the print() function. The output will be in the format of “The HCF of (num1) and (num2) is (hcf)”. For example :

Enter first number: 25
Enter second number: 36
The HCF of 25 and 36 is 1