GCD of two Numbers in Python

GCD, I’m very much sure you have learned this term in your school life. Let us discuss the definition of the GCD.

GCD is The Greatest Common Divisor, also known as the greatest common factor, highest common divisor, or highest common factor.

GCD of a set of numbers is the largest positive integer number that divides all the numbers in the set without remainder. It is the biggest multiple of all numbers in the set.

To Find the GCD

• Write all the factors of each number.
• Select the common factors.
• Select the greatest number as GCD.

Factors of 24 are 2, 2, 2, 3

Factors of 18 are 2, 2, 3

On Multiplying common Factors = 2 * 3

GCD of 24 and 18 = 6

We want you to know about the GCD of two numbers. Hence we are come up with the best video explanation you have ever watched on the internet, where you not only understand the logic but also code to get the desired output.

Do you still face difficulties in understanding the logic? That’s perfectly fine; we have something more for you. You can scroll down to learn more about this topic.

For all the practice Videos and Explanations on Python, please click over here. Python Practice Series.

Python Program to Print GCD of two Numbers

There are various methods to Get the GCD of two numbers in python. You can find the source code and an explanation of different methods over here. Let’s start with our program here.

GCD of Two Numbers in Python Using Recursion

#Python Program to print GCD of Two Numbers Using Recursion
def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))
GCD=gcd(a,b)
print("GCD is: ",GCD)

  

Output:

Enter first number:15
Enter second number:20
GCD is:  5

Video Explanation to Print GCD of two numbers in Python

Code Explanation Method 1: GCD of two numbers in Python 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. So Let’s accept two inputs from users a and b and convert it into an integer.

Pass the input numbers as an argument to a recursive function, which is gcd. Inside the gcd function, first, we have checked if b is equal to 0, then return number a, which means if the second number is zero, then return the first number.

The else section recursively calls the same function gcd with the second number as a first argument until it gets the remainder, which divides the second number by the first number.

Ultimately as the second number, which is b, will become zero, which means the remainder of the b/a becomes zero, then the function will return the a. Then display the GCD using the print statement. Let’s run this program and pass input as 15 and 20 for the first and second numbers. So the resultant output will be 5.

GCD of Two Numbers in Python Using In-Build Function

#Python Program to Print GCD of Two Numbers Using In-Build Function
#We are importing math function
import math
print("The GCD of 24 and 15 is : ",math.gcd(24, 15))


Output

The GCD of 24 and 15 is : 3

Code Explanation Method 2: GCD of Two Numbers in Python Using In-Build Function

Here we have a very small line of code to get the GCD of the two numbers. We have used the in-build function gcd. We have imported a math library to calculate the GCD of two numbers.

Then inside a print statement, with the message, we will call math.gcd function, which accepts 2 nonnegative integer values and returns absolute/positive values after calculating the GCD of given numbers. Here we have not taken input from the user; you can also take input from the user and pass it to a function but make sure you convert the same into an integer.

Then Output of the program will be The GCD of 24 and 15 is : 3

GCD of Two Numbers in Python Using Euclid’s algorithm AKA Euclidean Algorithm

#Python Program to Print GCD of Two Numbers Using Euclid’s algorithm AKA Euclidean Algorithm
def find_gcd(a,b):  
    while(b):  
        a, b = b, a % b  
    return a  
a = int(input("Enter the first number:")) 
b = int(input("Enter the second number:"))
num = find_gcd(a,b)
print("The GCD of two number a and b is:",num)


Output

Enter the first number:15
Enter the second number:20
The GCD of two number a and b is: 5

Code Explanation Method 3: GCD of Two Numbers in Python Using Euclid’s algorithm AKA Euclidean Algorithm

Euclid’s algorithm is an efficient method for finding the greatest common divisor of two numbers. It is the oldest algorithm that divides the greater number into smaller ones and takes the remainder. Again, it divides the smaller number from the remainder, and this algorithm continuously divides the number until the remainder becomes 0.

Suppose we want to calculate the H.C.F of two numbers, 24 and 18. Then we divide the 24 by 18; it returns the remainder of 6. Now we again divide the number 18 by 6, and then it returns the remainder 0. So, in this way, we get the H.C.F is 6.

Let’s accept two inputs from users a and b and convert it into an integer. Then pass a and b to the function find_gcd. Inside the find_gcd function, while loop will execute till b is non-zero, and if b is zero, then the loop will break and return the value of a. Let’s look inside the while loop; this statement a, b = b, a%b does a swapping of the values. And we are assigning results of a%b to b.

Let’s run this program and pass input as 15 and 20 for the first and second numbers. So the resultant output will be 5. I hope you are getting the idea of calculating the GCD of two numbers.

I am very much sure that now your concept is clear for the GCD of two numbers in Python.

About The Author