# GCD of Two Numbers in Python using For loop | Recursion | Function | Euclidean Algorithm

GCD of two numbers in __python__ using **for** loop, **recursion**, **function**, and **Euclidean Algorithm**.

In this article, you will learn how to find the gcd of two numbers in python using **for** loop, **recursion**, **function**, and **Euclidean Algorithm**.

### Example

**TWO POSITIVE INTEGER NUMBERS::
160
70**

**GCD = 10**

### What is GCD of Two Numbers?

`The`

**GCD**is the largest integer number of two positive integer numbers that can exactly divide both numbers without remaining a remainder.

You should have knowledge of the following topics in Python programming to understand this program:

- Python

function**input()** - Python

loop**while** - Python

loop**for** - Python
**Functions** - Python
**Recursion**

## GCD of Two Numbers in Python using While loop

- Create two variables named

&**p**

.**q** - Take the two input values and assign these to these variables
**p**&**q**. - Iterate the while loop until
**p**becomes equal to**q**. - Inside the while loop subtract variables
**p**&**q**from each other until the values of both variables are equal to each other. - When while loop completed its iteration then prints the
**GCD**number final output of the program.

```
# GCD of Two Numbers in Python using While loop
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())
# It will calculate the GCD
while p != q:
if p > q:
p -= q
else:
q -= p
# It will print the final output
print ("\nGCD =", p)
```

### Output

`TWO POSITIVE INTEGER NUMBERS::`

160

70

`GCD = 10`

### Explanation

In this given program, we have taken two inputs following:

& **160**

positive integer numbers from the user via the system console. After that, we applied the standard formula to calculate the **70****GCD** value of these input numbers.

After the whole calculation, It will return the **GCD** value

the final output of the above program.**10**

## GCD of Two Numbers in Python using For loop

- Create two variables named

&**p**

.**q** - Take the two input values and assign these to these variables
**p**&**q**. - Iterate the for loop from range

to**1**

and checks that**p + 1**

&**p % i**

both are remainder is equal to**q % i**

, then It will return the**0**

number.**GCD** - Print the final output of the program.

```
# GCD of Two Numbers in Python using For loop
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())
# It will calculate the GCD
for i in range (1, p + 1):
if i <= q:
if p % i == 0 and q % i == 0:
g = i
# It will print the final output
print ("\nGCD =", p)
```

## GCD of Two Numbers in Python using Recursion

```
# GCD of Two Numbers in Python using Recursion
# It's the recursive function to find the GCD
def gcd(x, y):
if x == y:
return x
else:
if x > y:
x = x - y
else:
y = y - x
return gcd (x, y)
# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())
# It will print the final output
print ("\nGCD =", gcd (p, q))
```

## GCD of Two Numbers in Python using Function

```
# GCD of Two Numbers in Python using Function
# It will find the GCD
def gcd(x, y):
while x != y:
if x > y:
x = x - y
else:
y = y - x
return x
# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())
# It will print the final output
print ("\nGCD =", gcd (p, q))
```

### Output

`TWO POSITIVE INTEGER NUMBERS::`

190

60

`GCD = 10`

## GCD of Two Numbers in Python using Euclidean Algorithm

### Euclidean Algorithm:

- Euclidean Algorithm is a method or procedure for finding the greatest common

divisor of two positive integer numbers.**GCD** - The largest number of two
**GCD**numbers

&**p**

will divide each other without leaving the remainder.**q** **Algorithm**:- Let
**x**and**y**be the two input numbers **x**modulus

-->**y = R****(x % y)**- Let

and**x = y****y = R** - Repeat steps
**2**&**3**until**x**mod**y**is greater than 0 **GCD**number =**y**- Finished

- Let

```
# GCD of Two Numbers in Python using Euclidean Algorithm
# It's the recursive function to find GCD
def gcd(x, y):
return y if x == 0 else (x if y == 0 else x if x == y else (gcd(x - y, y) if x > y else gcd(x, y - x)))
# It's the driver code
p, q = None, None # To store the two positive numbers
print ("TWO POSITIVE INTEGER NUMBERS::")
p = int (input ())
q = int (input ())
# It will print the final output
print ("\nGCD =", gcd(p, q))
```

### Output

`TWO POSITIVE INTEGER NUMBERS::`

295

35

`GCD = 10`