Python Program to Find HCF or GCD of Two Numbers

Find HCF or gcd of two numbers in python; Through this tutorial, i am going to show you how 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.

Python Programs to Find HCF or GCD

  • 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

See the following steps to implement program to find HCF of two numbers using while loop in python:

  • Get input two number from the user in program
  • 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

See the following steps to implement python program to find HCF or gcd of two numbers using for loop:

  • Get 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

See the following steps to implement program to find hcf or gcd of two numbers using recursion function in python:

  • Define a function recursion
  • Get 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

Recommended Python Tutorials

Leave a Comment