 # gcd() in Python

## gcd() in Python

The Highest Common Factor (HCF) , also called gcd, can be computed in python using a single function offered by math module and hence can make tasks easier in many situations.

Naive Methods to compute gcd
1. Using Recursion:
 `# 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``))`

Output:

```The gcd of 60 and 48 is : 12
```

2. 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``))`

Output:

```The gcd of 60 and 48 is : 12
```
3. Using 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``))`

Output:

```The gcd of 60 and 48 is : 12
```
Using math.gcd() function of Python

Using gcd() can compute the same gcd with just one line.

```math.gcd( x, y )
Parameters :
x :  Non-negative integer whose gcd has to be computed.
y : Non-negative integer whose gcd has to be computed.
Return Value :
This method will return an absolute/positive integer value after
calculating the GCD of given parameters x and y.
Exceptions :
When Both x and y are 0, function returns 0, If any number is a character ,
Type error is raised.
```
 `# 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``))`

Output:

```The gcd of 60 and 48 is : 12
```
Common Exceptions

Some common Exceptions in this function are :

• Both numbers are 0, gcd is 0
• If only either number is Not a number, Type Error is raised.
 `# Python code to demonstrate gcd()` `# method exceptions` ` ` `import` `math` ` ` `# prints 0` `print` `(``"The gcd of 0 and 0 is : "``,end``=``"")` `print` `(math.gcd(``0``,``0``))` ` ` `# Produces error` `print` `(``"The gcd of a and 13 is : "``,end``=``"")` `print` `(math.gcd(``'a'``,``13``))`

Output:

```The gcd of 0 and 0 is : 0
The gcd of a and 13 is :
```

Runtime Error :

```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
```

Last Updated on October 27, 2021 by admin

## Python String ConcatenationPython String Concatenation

Python String Concatenation In Python, Strings are arrays of bytes representing Unicode characters. However, Python does not have a character data type, a single character is simply a string with a length of 1. Square brackets [] can be used to access

## Add multiple columns to dataframe in PandasAdd multiple columns to dataframe in Pandas

Add multiple columns to dataframe in Pandas In Pandas, we have the freedom to add columns in the data frame whenever needed. There are multiple ways to add columns to the Pandas data frame. Method 1: Add multiple columns to

## How to take integer input in Python?How to take integer input in Python?

How to take integer input in Python? In this post, We will see how to take integer input in Python. As we know that Python built-in input() function always returns a str(string) class object. So for taking integer input we

## Python – How to make a terminal progress bar using tqdmPython – How to make a terminal progress bar using tqdm

Python | How to make a terminal progress bar using tqdm Whether you’re installing software, loading a page or doing a transaction, it always eases your mind whenever you see that small progress bar giving you an estimation of how

## Context Manager in PythonContext Manager in Python

Context Manager in Python Managing Resources : In any programming language, the usage of resources like file operations or database connections is very common. But these resources are limited in supply. Therefore, the main problem lies in making sure to release

## Python String isnumeric() MethodPython String isnumeric() Method

Python String isnumeric() Method Python String isnumeric() method is a built-in method used for string handling. The issnumeric() method returns “True” if all characters in the string are numeric characters, Otherwise, It returns “False”. This function is used to check if the

## Creating a Pandas SeriesCreating a Pandas Series

Pandas Series is a one-dimensional labelled array capable of holding data of any type (integer, string, float, python objects, etc.). The axis labels are collectively called index. Labels need not be unique but must be a hashable type. The object

## Python List index() MethodPython List index() Method

Python List index() index() is an inbuilt function in Python, which searches for a given element from the start of the list and returns the lowest index where the element appears. Syntax: list_name.index(element, start, end) Parameters:  element – The element whose lowest