Python program to find HCF or GCD of two numbers

Summary:

Problem Description: Write a Python program to find the Highest common factor (HCF) or Greatest Common divisor (GCD) of two numbers.

Description: The HCF of two numbers is the highest number which completely divides both the numbers. HCF and GCD are same things.

Example:

Input: 30 50
Output: HCF of 30 and 50 is 10.
Explanation: 10 is highest number which completely divides 30 and 50 and leave remainder 0.

Input: 46 23
Output: HCF of 40 and 23 is 23.
Explanation: 23 is highest number which completely divides 23 and 46 and leave remainder 0.

Input: 17 19
Output: HCF of 17 and 19 is 1.
Explanation: 1 is highest number which completely divides 17 and 19 and leave remainder 0.

Hint: Loop through 1 to the smaller number between both. Find the highest number which completely divides both.

Now you got the hint, you should try to write a Python program to find HCF or GCD of two numbers.

Python Program: Find HCF or GCD of two numbers

hcf.py

Copy

#Using loop

def find_hcf(num1, num2):
    smallerNum = min(num1, num2)
    gcd = 1
    for i in range(1, smallerNum+1):
        if(num1%i==0 and num2%i==0):
            gcd = i
    return gcd


num1 = 50
num2 = 40

#num1,num2 = map(int, input("Enter two numbers separated by space:\n").split(" "))

print("GCD of {0} and {1} is {2}".format(num1, num2, find_hcf(num1, num2)))

Output

GCD of 50 and 40 is 10

The program implements the same logic as given in the hint.

The function find_hcf() takes two argument num1 and num2 to calculate HCF or GCD.

The next step is to find the smaller of the two numbers using the min() function.

The inbuilt min() function of Python returns the smallest number of any iterable or elements passed to it.

Then we iterate through 1 to the smaller number among both number (inclusive) and find the highest number which divides them both.

Related Python Examples: