Finding The Highest Common Factor(HCF) Of Two Numbers In Python

In mathematics, the terms- Highest Common Factor(HCF) and Greatest Common Divisor(GCD) mean the same thing. HCF of a two or more number is a single highest number that perfectly divides all the number without leaving a remainder. For example, consider 18 and 24 be two numbers. Then their HCF is 6 since it divides them without leaving any remainder. No any number above 6 can divide both of them perfectly. The following code in python can be used to find the HCF of two numbers and I have done it very simply without using any functions or complex logic.

a = int(input("Enter the first number: "))

b = int(input("Enter the second number: "))

if a > b:
    lesser_number = b
else:
    lesser_number = a

for i in range(1, lesser_number + 1):
    if a % i == 0 and b % i == 0:
        hcf = i
print("The highest common factor of {} and {} is {}".format(a, b, hcf))

Lets see the sample output for this code by providing two numbers 3 and 6 as below:

First the program prompts user to enter two number. Say you enter 3 and 6. After that the program checks for the smaller number between 3 and 6 which is 3 itself. After that the program will run for-loop starting from 1 to smaller number plus one which is 4. Doing so the loop will continue until the value of i is 3.

At first i=1 and the if condition inside the for loop evaluates to True since 3%1 and 6%1 both leaves remainder 0 hence hcf becomes 1. Now i will be 2 and the if condition this time will evaluate to false since 3%2 doesn't leave remainder value 0. Now when i=3, the if condition again evalautes to true since 3%3 and 6%3 both leaves remainder value zero. So hcf, which stores the value of 1 during first iteration now will be replaced by 3. The loop terminates as specified by the condition and we therefore have the highest common factors of the number we want to find.