**Python program to find the GCD (Greatest Common Divisor) of two numbers using three different methods, including the built-in method**

## Example 1: Using Euclidean Algorithm

The Euclidean Algorithm is a simple and fast way to find the biggest number that can divide two other numbers without leaving a remainder.

Here’s the formula for the Euclidean Algorithm, where `a`

and `b`

are two positive integers, and `gcd(a, b)`

is the greatest common divisor of `a`

and `b`

### Method 1: Using GCD Euclidean Algorithm formula

```
gcd(a, b) = gcd(b, a mod b)
```

Implementing Euclidean algorithm in Python to find the GCD of two numbers.

```
# Using Euclidean Algorithm
def gcd_euclidean(a, b):
if b == 0:
return a
else:
return gcd_euclidean(b, a % b)
# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
# Finding GCD using Euclidean Algorithm
gcd = gcd_euclidean(a, b)
print(f"GCD of {a} and {b} using Euclidean Algorithm is: {gcd}")
```

### Output

```
Enter first number: 12
Enter second number: 103
GCD of 12 and 103 using Euclidean Algorithm is: 1
```

This above program finds the biggest number that can divide two other numbers without leaving a remainder by repeating a simple calculation until it can’t be done anymore.

## Method 2: Using an iterative approach

In this program, we use a Python while loop to find the biggest number that can divide two other numbers without leaving a remainder by repeating a simple calculation until it can’t be done anymore.

```
def gcd_iterative(a, b):
while b:
a, b = b, a % b
return a
# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
# Finding GCD using iterative approach
gcd = gcd_iterative(a, b)
print(f"GCD of {a} and {b} using iterative approach is: {gcd}")
```

### Output

```
Enter first number: 88
Enter second number: 12
GCD of 88 and 12 using iterative approach is: 4
```

## Method 3: Using built-in function

This program uses a function that already exists in Python to find the biggest number that can divide two other numbers without leaving a remainder.

```
# Using built-in function
import math
# Taking input from user
a = int(input("Enter first number: "))
b = int(input("Enter second number: "))
# Finding GCD using built-in function
gcd = math.gcd(a, b)
print(f"GCD of {a} and {b} using built-in function is: {gcd}")
```

```
Enter first number: 97
Enter second number: 8369
GCD of 97 and 8369 using built-in function is: 1
```

## Conclusion

The above three ways to find the biggest number that can divide two other numbers without leaving a remainder are ** Euclidean Algorithm, iterative approach, and built-in function**. All three methods are easy to use and can help us solve problems in math and programming