Python Program to Find HCF or GCD

Here we have provided two python source code to find the GCD or HCF of two numbers.

Prerequisite topics to create this program.

• Python Input, Output
• Python User-Defined Function
• Python Recursion
• Python if...else statements
• Python For loop

There are two common techniques we can use to find the HCF of two numbers, one is by using the function & loop and other is by using the Euclidean Algorithm HCF or GCD: HCF (Highest Common Factor) or GCD(Greatest Common Divisor) of two numbers is the largest positive integer which divides both the numbers perfectly. for example, the HCF of 6 and 9 is 3, because 3 is the largest number which can divide 9 and 6 completely. The HCF of two number always reside between the range of 1 to the smallest number. If there is no largest number which can divide both the numbers then the HCF of those two numbers is 1.

Python Program HCF of two number using for loop

Steps:

• First, ask the user to enter the two numbers.
• Now using the comparison operator find the smaller number.
• Create a loop from 1 to the smallest number (included).
• using the comparison, arithmetic and logical operator we will find that number which can divide both the number perfectly.
• And if a number divides the both completely then that would be the HCF of both the number.

Code:

def find_hcf(x, y):
    # Find the smallest number
    if x > y:
        smallest = y
    else:
        smallest = x
    for i in range(1, smallest+1):
        if((x % i == 0) and (y % i == 0)):
            hcf = i 
    return hcf

n1= int(input("Enter the First Number: "))
n2= int(input("Enter the Second Number: "))

print("The H.C.F. of", n1 ,"and",n2 ,"is:", find_hcf(n1, n2))

Output 1:

Enter the First Number: 54
Enter the Second Number: 24
The H.C.F. of 54 and 24 is: 6

Output 2:

Enter the First Number: 100
Enter the Second Number: 99
The H.C.F. of 100 and 99 is: 1

Find the HCF using Euclidean Algorithm

In the Euclidean algorithm, we divide the larger number by the smaller number and calculate the remainder, then we divide the smaller number with the remainder, again calculate the remainder, and repeat this process until we get the remainder 0. for instance, if we want to find the HCF of 6 and 9, first we divide 9 with 6 because 9 is larger than 6, when we divide 9 by 6 we get 3 as a remainder, now using the remainder 3 we divide 6, and when we divide 6 by 3 we get 0 as a remainder which mean 3 is the HCF of 6 and 9. 9%6=3 6%3=0 HCF=3

Steps:

• First, we will ask the user to enter two values.
• By using the comparison operator we will find the smaller number.
• Now start a while loop which continuously runs till the remainder get 0.
• Once the remainder is 0 we print the value of HCF.

Python Code:

def find_hcf(x, y):
    # Find the smallest number
    if x > y:
        smaller = y
        larger=x 
    else:
        smaller = x
        larger=y
    while(smaller):
        smaller,larger = larger%smaller, smaller
    return larger

n1= int(input("Enter the First Number: "))
n2= int(input("Enter the Second Number: "))

print("The H.C.F. of", n1 ,"and",n2 ,"is:", find_hcf(n1, n2))

Output 1:

Enter the First Number: 11
Enter the Second Number: 11
The H.C.F. of 11 and 11 is" 11

Output 2:

Enter the First Number: 50
Enter the Second Number: 55
The H.C.F. of 50 and 55 is: 5

People are also reading:

• C Program to Extract a Portion of String
• WAP in C++ & Python to Insert an Element in an Array
• C Program to Convert Feet into Inches
• WAP to calculate the average marks of 5 subjects
• Python RegEx
• WAP in C to check whether the number is a Palindrome number or not
• Python Program to Add Two Numbers
• Binary Search in C
• Python Program to Solve Quadratic Equation
• WAP in C++ and python to check whether the number is even or odd