HCF

The greatest common divisor of two or more numerical values is called the highest common factor (HCF). In other words, the largest number that can completely divide two or more numbers is the highest common factor.

Logic

Let declare one temporary variable hcf by 1, we are going to use this variable to store HCF.

Here we are calculating HCF of two user given numbers, after taking both the numbers (num1, num2) from the user, we have to find out which number is smaller, we store the minimum one in the variable min.

Now we start one loop from 1 to min (Minimum between both numbers), and inside the loop, we have to check if both the numbers are completely divisible by current number “i” or not. If yes then we update temporary variable hcf by current number “i”, otherwise continue with the loop.

Once the loop is over simply print the variable hcf containing the highest common factor of num1 and num2.

Program

FindHCF.pyCopy
# Take input from user
num1 = int(input("Enter 1st number : "))
num2 = int(input("Enter 2nd number : "))

# Find minimum between two numbers
min = num1
if num2 < num1:
    min = num2

for i in range(1, min + 1):
    if((num1 % i) == 0 and (num2 % i) == 0):
            hcf = i

print("\nHCF of", num1, "and", num2, ":", hcf)
Try It

Output

Enter two numbers : 12 30
HCF of 12 and 30 : 6