How To Implement GCD In Python?

In school and college, we have all learnt the basics of mathematics. Among all the complex concepts of trigonometry and arithmetic’s, one concept that is used most often in programming is that of the GCD or Greatest Common Divisor. Similar to all programming languages, Python too supports the creation of a code that will be able to find the GCD of two numbers given by the user and in this article we will learn how to do just that. Let us see how to implement GCD in Python,

So let us get started,

What Is GCD?

GCD is the abbreviation for Greatest Common Divisor which is a mathematical equation to find the largest number that can divide both the numbers given by the user. Sometimes this equation is also referred as the greatest common factor. For example, the greatest common factor for the numbers 20 and 15 is 5, since both these numbers can be divided by 5. This concept can easily be extended to a set of more than 2 numbers as well, where the GCD will be the number which divides all the numbers given by the user.

The concept of GCD has a wide number of applications in number theory, particularly that of encryption technology that is RSA as well as modular arithmetic. It is also sometimes used for simplifying fractions that are present in an equation.

Now that you know the basic concept of GCD, let us see how we can code a program in Python to execute the same.

GCD In Python

In order to compute GCD in Python we need to use the math function that comes in built in the Python library. Let us explore a couple of examples to understand this better.

Let us see how to find GCD in Python Using Recursion

GCD Using Recursions

# Python code to demonstrate naive 
# method to compute gcd ( recursion ) 
def hcfnaive(a,b): 
	if(b==0): 
		return a 
	else: 
		return hcfnaive(b,a%b) 
a = 60
b= 48
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (hcfnaive(60,48)) 

When the above program is run, the output will look something like this.

The gcd of 60 and 48 is : 12

We can also gind GCD using loops,

GCD Using Loops

# Python code to demonstrate naive 
# method to compute gcd ( Loops ) 

def computeGCD(x, y): 
	if x > y: 
		small = y 
	else: 
		small = x 
	for i in range(1, small+1): 
		if((x % i == 0) and (y % i == 0)): 
			gcd = i 	
	return gcd 
a = 60
b= 48
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (computeGCD(60,48)) 

When the above program is executed, the output will look like this.

The gcd of 60 and 48 is : 12

Let us see the next method,

GCD Using The Euclidean Algorithm

# Python code to demonstrate naive 
# method to compute gcd ( Euclidean algo ) 
def computeGCD(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 
a = 60
b= 48  
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (computeGCD(60,48))

The output for the above mentioned program will be,

The gcd of 60 and 48 is : 12

Moving on, below is the fourth method to find GCD in Python,

GCD Using Math GCD Function

Before we can make use of the math.gcd() function to compute the GCD of numbers in Python, let’s take a look at its various parameters.

Syntax: math.gcd( x,y)

Parameters

X: is the non negative integer whose gcd needs to be computed.

Y: is the second non negative integer whose gcd needs to be computed.

Return Value: This parameter will return an absolute positive return value after it has computed the GCD of both the numbers inputted by the user.

Exceptions: If in a certain situation, both the numbers inputted by the user is zero, then the function will return zero; and if the input is a character, then the function will return an error.

LLet us see the sample code,

# Python code to demonstrate gcd()
# method to compute gcd
import math
# prints 12
print ("The gcd of 60 and 48 is : ",end="")
print (math.gcd(60,48))

The output of the above program will be,

The gcd of 60 and 48 is : 12

Common Exceptions

Here are the most common exceptions for using this function.

1. If either of the numbers inputted by the user is a zero, then the function will return zero.
2. If either of the inputs are a character, then the function will return a type error.

To understand this better, take a look at the example below.

# Python code to demonstrate gcd() 
# method to compute gcd 
import math 
# prints 12 
print ("The gcd of 60 and 48 is : ",end="") 
print (math.gcd(60,48)) 

The output for the above program will be,

The gcd of 0 and 0 is : 0

The gcd of a and 13 is :

When run the above program will also return a runtime error, which will look something like this.

Traceback (most recent call last):

  File “/home/94493cdfb3c8509146254862d12bcc97.py”, line 12, in

    print (math.gcd(‘a’,13))

TypeError: ‘str’ object cannot be interpreted as an integer

So this brings us to the end of this article on GCD in Python.

To get in-depth knowledge on Python along with its various applications, you can enroll now for the best Python course online training with 24/7 support and lifetime access. Got a question for us? Mention them in the comments section of  this article and we will get back to you.