# Greatest common divisor (GCD) in Python

In this post, you will learn how to find the **greatest common divisor (G.C.D)** or **highest common factor (H.C.F)** of numbers using different methods in **Python** programming language.

Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted **gcd(a,b)**. These are different ways to find the GCD or HCF using Python.

## GCD in Python using math.gcd() Method

In Python, the **math** module contains various mathematical functions, which can be performed effortlessly utilizing the module. The **math.gcd()** method computes the greatest common divisor of two numbers.

**Syntax of math.gcd()**

**math.gcd(x, y)**

Here, **x** and **y** are non-negative integers for computing GCD. It returns a positive integer value representing the greatest common divisor (GCD) for two integers.

**Python gcd Example**

```
import math
# Greatest common divisor of the two integers
print("GCD of (5, 2) = ",math.gcd(5, 2))
print("GCD of (4, 10) = ",math.gcd(4, 10))
print("GCD of (10, 0) = ",math.gcd(10, 0))
print("GCD of (-9, -16) = ",math.gcd(-9, -16))
print("GCD of (4, 14) = ",math.gcd(4, 14))
print("GCD of (6, 3) = ",math.gcd(6, 3))
```

**Output of the above code-**

```
GCD of (5, 2) = 1
GCD of (4, 10) = 2
GCD of (10, 0) = 10
GCD of (-9, -16) = 1
GCD of (4, 14) = 2
GCD of (6, 3) = 3
```

## GCD in Python using for loop

Here, we define a function to compute the **H.C.F** of two numbers and return it. In each iteration, we check if our number perfectly divides both the user input numbers. If this is true, we store the number as H.C.F. At the completion of the loop, we conclude with the largest number that perfectly divides both the numbers.

```
# Python program to find GCD of two numbers
# define a function
def get_gcd(a, b):
# pick the smaller number
if a > b:
smaller = int(b)
else:
smaller = int(a)
for i in range(1, smaller+1):
if((a % i == 0) and (b % i == 0)):
gcd = i
return gcd
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", get_gcd(int(x), int(y)))
```

**Output of the above code-**

```
Enter the first number: 39
Enter the second number: 2
The G.C.D. is 1
Enter the first number: 48
Enter the second number: 34
The G.C.D. is 2
```

## GCD in Python using while loop

In the given Python program, we have used the while loop to compute the GCD of two numbers.

```
x = int(input('Please input the first integer:'))
y = int(input('Please input the second integer:'))
while y != 0:
gcd = y
y = x % y
x = gcd
print("The G.C.D. is ",gcd)
```

**Output of the above code:**

```
Please input the first integer:6
Please input the second integer:10
The G.C.D. is 2
```

## GCD in Python using Recursion

**Recursion function** is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.

```
def compute_gcd(a, b):
if(b == 0):
return a
else:
return compute_gcd(b, a % b)
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", compute_gcd(int(x), int(y)))
```

**Output of the above code-**

## GCD in Python using Euclidean algorithm

The **Euclidean algorithm** is an efficient way to find the greatest common divisor of two numbers, the largest number that divides them both without a remainder.

**Example**

```
# Function to find GCD the Using Euclidian algorithm
def compute_gcd(a, b):
while(b):
a, b = b, a % b
return a
x = input("Enter the first number: ")
y = input("Enter the second number: ")
print("The G.C.D. is ", compute_gcd(int(x), int(y)))
```

**Output of the above code-**

```
Enter the first number: 78
Enter the second number: 40
The G.C.D. is 2
Enter the first number: 30
Enter the second number: 15
The G.C.D. is 15
```

### Related Articles

**
Python program to multiply two numbers
Insert XML Data to MySQL Table using Python
Remove last element from list Python
Multiply all elements in list Python
ASCII value in Python Python String isalpha() Method Python YouTube Downloader with Pytube Python alphabetical order Pandas Converting Strings to datetime Pandas fillna multiple columns Stemming and Lemmatization in Python Python | Generate QR Code using pyqrcode module Extract text from image Python How to Send Text Messages With PHP Fibonacci Series In Python | Python Program To Print File Handling in Python How to convert XML to JSON in Python Python XML to Dictionary Serialize Python dictionary to XML**