Find HCF or gcd of two numbers in python; In this tutorial, you will learn how do you write a program to find HCF and gcd of two numbers in python using a while loop, for loop and recursion function.
The HCF (Highest Common Factor) of two numbers is the highest number among all the common factors of the given numbers. For example, the HCF of 12 and 36 is 12 because 12 is the highest common factor of 12 and 36.
Programs to Find HCF or GCD
Let’s use the following algorithm to write a program to find gcd or hcf of two numbers in python:
- HCF of Two Numbers in Python using While Loop
- Python Program to Find HCF of Two Numbers using For loop
- Python Program to Calculate HCF (GCD) Using Recursive Function
HCF of Two Numbers in Python using While Loop
Follow the below steps and write a program to find HCF of two numbers using while loop in python:
- Take input two number from the user
- Iterate while loop and find HFC Or GCD
- Then inside in loop store HFC Or GCD value in variable
- Print HFC Or GCD of given number
# Python program to find H.C.F of two numbers using while loop
# taking input from users
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
i = 1
while(i <= num1 and i <= num2):
if(num1 % i == 0 and num2 % i == 0):
gcd = i
i = i + 1
print("The H.C.F. of", num1,"and", num2,"is", gcd, "".format(num1, num2, gcd))
Output
EntEnter first number: 36 Enter second number: 12 The H.C.F. of 36 and 12 is 12
Python Program to Find HCF of Two Numbers using For loop
Follow the below steps and write python program to find HCF or gcd of two numbers using for loop::
- Take input two number from the user
- Iterate for loop to find HFC Or GCD and store HFC Or GCD value in variable
- Print HFC Or GCD of given number
# Python program to find H.C.F of two numbers
# define a function
def compute_hcf(x, y):
# choose the smaller number
if x > y:
smaller = y
else:
smaller = x
for i in range(1, smaller+1):
if((x % i == 0) and (y % i == 0)):
hcf = i
return hcf
# taking input from users
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print("The H.C.F. of", num1,"and", num2,"is", compute_hcf(num1, num2))
Output
Enter first number: 52 Enter second number: 24 The H.C.F. of 52 and 24 is 4
Python Program to Find HCF of Two Numbers using Recursion Function
Follow the below steps and write program to find hcf or gcd of two numbers using recursion function in python:
- Define a function recursion
- Take input two number from the user
- Call recursion function to find HFC Or GCD and store HFC Or GCD value in variable
- Print HFC Or GCD of given number
# Finding HCF (GCD) using Recursive Function
# Defining function
def hcf(a,b):
if b==0:
return a
else:
return hcf(b, a%b) # this is recursion as hcf() calls itself
# Reading numbers from user
num1 = int(input('Enter first number: '))
num2 = int(input('Enter second number: '))
# Function call & displaying output HCF (GCD)
print("The H.C.F. of", num1,"and", num2,"is", hcf(num1, num2))
Output
Enter first number: 8 Enter second number: 12 The H.C.F. of 8 and 12 is 4
