# 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

## Counting the frequencies in a list using dictionary in PythonCounting the frequencies in a list using dictionary in Python

Counting the frequencies in a list using dictionary in Python   Given an unsorted list

## Lambda and filter in PythonLambda and filter in Python

Lambda and filter in Python Examples Given a list of numbers, find all numbers divisible

## Different ways to clear a list in PythonDifferent ways to clear a list in Python

Different ways to clear a list in Python   There are many ways of clearing

## Python – Convert number to list of integersPython – Convert number to list of integers

Python | Convert number to list of integers The interconversion of data types is a

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

Python List index() index() is an inbuilt function in Python, which searches for a given element

## Python | Change column names and row indexes in Pandas DataFramePython | Change column names and row indexes in Pandas DataFrame

Python Pandas – Change column names and row indexes in Pandas DataFrame   Given a

## Python – Get dictionary keys as a listPython – Get dictionary keys as a list

Python | Get dictionary keys as a list   Given a dictionary, write a Python

## Python join() functionPython join() function

Python join() function The join() method is a string method and returns a string in