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 is 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.

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 the this topic.

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

Video Explanation to Print GCD of two numbers in Python

Code: GCD of two Numbers in Python

There are various methods to Get the GCD of two numbers in python. You can find source code and an explanation of different methods over here.

Let’s start with our program here.

Method 1: GCD of two number using Recursion

Source Code and Output

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

Code Explanation Method 1: GCD of two number 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 user 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 means the remainder of the b/a become zero then the function will return the a.

Then display the GCD using print statement

Let’s run this program and pass input as 15 and 20 for the first and second number.

So the resultant output will be 5.

Method 2: GCD Using Euclid’s algorithm AKA Euclidean Algorithm

Source Code and Output

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 2: GCD Using Euclid’s algorithm AKA Euclidean Algorithm

Euclid’s algorithm is an efficient method to find 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 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 user 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 loop will break and return the value of a.

Lets look inside while loop, this statement a, b = b, a%b does swapping of the values. And we are assigning result of a%b to b.

Let’s run this program and pass input as 15 and 20 for the first and second number.

So the resultant output will be 5.

I hope you are getting the idea of calculating GCD of two numbers.

Method 3:  GCD Using In-Build Function

Source Code and Output

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 3: GCD Using In-Build Function

Here we have very small line of code to get 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 value after calculating the GCD of given numbers.

Here we have not taking input from user, you can also take input from user and pass it to 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

I am very much sure, now your concept is clear for GCD of two numbers.

Facebook Comments
(Visited 1 times, 1 visits today)

Leave A Comment

Your email address will not be published. Required fields are marked *