HCF or GCD of Two Numbers in Python

In the previous program, we developed a Python program to find the lcm (Least or lowest common multiple) of two numbers. Now in this post, we will develop the HCF or GCD program in Python to find the HCF or GCD of two numbers.

The highest common factor (HCF) of two or more numbers is the greatest number that divides each of them exactly. Greatest Common Measure(GCM) and Greatest Common Divisor(GCD) are the other terms used to refer to HCF.

Example: HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.

GCD in Python

This is a normal method to find HCF or GCD of the two numbers in python. We will take two numbers while declaring the variables. Python program to find GCD of the two numbers using for loop and if-else statement.

# Python program to find GCD of two numbers

# take inputs
x = int(input('Enter First Number: '))
y = int(input('Enter Second Number: '))

# choose the smaller number
if x > y:
    smaller = y
else:
    smaller = x
    
# find gcd of the number
for i in range (1,smaller+1):
    if((x % i == 0) and (y % i == 0)):
        gcd = i

# display result
print('The GCD of',x,'and',y,'is',gcd)

Output for the different input value:-

Enter First Number: 2
Enter Second Number: 10
The GCD of 2 and 10 is 2

Enter First Number: 8
Enter Second Number: 100
The GCD of 8 and 100 is 4

In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as GCD. At the completion of the loop, we end up with the largest number that perfectly divides both the numbers.

Greatest Common Divisor Python Program

In the previous program, find the GCD or HCF of the two numbers using for loop but in this program, find the factorial of the number using while loop.

# Python program to find GCD of two numbers

# take inputs
x = int(input('Enter First Number: '))
y = int(input('Enter Second Number: '))

# find gcd of the numbers
i = 1
while(i <= x and i <= y):
    if(x % i == 0 and y % i == 0):
        gcd = i
    i += 1

# display result
print('The GCD of',x,'and',y,'is',gcd)

Output:-

Enter First Number: 45
Enter Second Number: 16
The GCD of 45 and 16 is 1

HCF or GCD Program in Python using Function

We can also take the help of a function to find the HCF or GCD of the two numbers in python. A function is a block of code that performs a specific task.

# Python program to find GCD of two numbers using function

def compute_gcd(x, y):  #user-defined function
    # 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)):
            gcd = i 
    return gcd

# take inputs
num1 = int(input('Enter First Number: '))
num2 = int(input('Enter Second Number: '))

# calling function & display result
print('The GCD of',num1,'and',num2,'is',compute_gcd(num1, num2))

Output:-

Enter First Number: 75
Enter Second Number: 80
The GCD of 75 and 80 is 5

Python Program to Find GCD of Two Numbers using Recursion

We can also use the recursion technique to find the GCD or HCF of two numbers. A technique of defining the method/function that contains a call to itself is called recursion. The recursive function/method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

# Python program to find GCD of two numbers using recursion

def recur_gcd(x, y):  # user-defined function
    if(y == 0):
        return x
    else:
        return recur_gcd(y, x%y)

# take inputs
num1 = int(input('Enter First Number: '))
num2 = int(input('Enter Second Number: '))

# calling function & display result
print('The GCD of',num1,'and',num2,'is',recur_gcd(num1, num2))

Output:-

Enter First Number: 50
Enter Second Number: 1200
The GCD of 50 and 1200 is 50

HCF in Python using Euclidean Algorithm

This method is much more efficient to find the GCD of two numbers in python. This algorithm is based on the fact that the GCD of two numbers divides their difference as well. We divide the greater by smaller and take the remainder. Then, divide the smaller by this remainder. Repeat until the remainder is 0.

# Python program to find GCD of two numbers 
# using Euclidean Algorithm

def compute_gcd(x, y):  # user-defined function
    while(y):
        x, y = y, x%y
    return x

# take inputs
num1 = int(input('Enter First Number: '))
num2 = int(input('Enter Second Number: '))

# calling function & display result
print('The GCD of',num1,'and',num2,'is',compute_gcd(num1, num2))

Output:-

Enter First Number: 15
Enter Second Number: 145
The GCD of 15 and 145 is 5

This statement x, y = y, x%y does swapping of the values. Click here to learn more about How to swapping variables in python.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search