 # Python program to find the gcd of two numbers

## Python program to find the gcd of two numbers

Given two numbers. The task is to find the GCD of the two numbers.

Using STL :

In Python, the math module contains a number of mathematical operations, which can be performed with ease using the module. math.gcd() function compute the greatest common divisor of 2 numbers mentioned in its arguments.

Syntax: math.gcd(x, y)

Parameter:

: Non-negative integer whose gcd has to be computed.

: Non-negative integer whose gcd has to be computed.

Returns: 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 the working of gcd()` `# importing "math" for mathematical operations` `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
```

Using Recursion :

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

Output

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

Using Euclidean Algorithm :

The Euclid’s algorithm (or Euclidean Algorithm) is a method for efficiently finding the greatest common divisor (GCD) of two numbers. The GCD of two integers X and Y is the largest number that divides both of X and Y (without leaving a remainder).

Pseudo Code of the Algorithm-

1. Let  a, b  be the two numbers
2. a mod b = R
3. Let  a = b  and  b = R
4. Repeat Steps 2 and 3 until  a mod b  is greater than 0
5. GCD = b
6.  Finish
 `# Recursive function to return gcd of a and b` `def` `gcd(a, b):` ` ` `    ``# Everything divides 0` `    ``if` `(a ``=``=` `0``):` `        ``return` `b` `    ``if` `(b ``=``=` `0``):` `        ``return` `a` ` ` `    ``# base case` `    ``if` `(a ``=``=` `b):` `        ``return` `a` ` ` `    ``# a is greater` `    ``if` `(a > b):` `        ``return` `gcd(a``-``b, b)` `    ``return` `gcd(a, b``-``a)` ` ` `# Driver program to test above function` `a ``=` `98` `b ``=` `56` `if``(gcd(a, b)):` `    ``print``(``'GCD of'``, a, ``'and'``, b, ``'is'``, gcd(a, b))` `else``:` `    ``print``(``'not found'``)`

Output

`GCD of 98 and 56 is 14`

Last Updated on March 1, 2022 by admin

## Python – Remove all values from a list present in other listPython – Remove all values from a list present in other list

Python | Remove all values from a list present in other list Sometimes we need to perform the operation of removing all the items from the lists that are present in another list, i.e we are given some of the

## Find the k most frequent words from data set in PythonFind the k most frequent words from data set in Python

Find the k most frequent words from data set in Python Given the data set, we can find k number of most frequent words. In order to do this, we’ll use a high performance data type module, which is collections. This

## Python – Convert list into list of listsPython – Convert list into list of lists

Python | Convert list into list of lists Given a list of strings, write a Python program to convert each element of the given list into a sublist. Thus, converting the whole list into a list of lists. Examples:

## Saving a Video using OpenCVSaving a Video using OpenCV

Saving a Video using OpenCV OpenCV is an open-source and most popular computer vision library that contains several computer vision algorithms. You can read, display, write and doing lots of other operations on images and videos using OpenCV. The OpenCV

## Python – Itertools.chain()Python – Itertools.chain()

Python – Itertools.chain() The itertools is a module in Python having a collection of functions that are used for handling iterators. They make iterating through the iterables like lists and strings very easily. One such itertools function is chain(). Note: For more information, refer

## Python – pass multiple arguments to map functionPython – pass multiple arguments to map function

Python – pass multiple arguments to map function The map() function is a built-in function in Python, which applies a given function to each item of iterable (like list, tuple etc) and returns a list of results or map object.

## struct module in Pythonstruct module in Python

struct module in Python This module performs conversions between Python values and C structs represented as Python bytes objects. Format strings are the mechanism used to specify the expected layout when packing and unpacking data. Module struct is available in

## get_attribute() element method – Selenium Pythonget_attribute() element method – Selenium Python

get_attribute() element method – Selenium Python get_attribute() element method – Selenium Python Difficulty Level : Basic Last Updated : 27 Apr, 2020 Selenium’s Python Module is built to perform automated testing with Python. Selenium Python bindings provides a simple API to write