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