Euclidean Algorithm implementation written in Python.

### Subtraction-based version:

#### Iteration version:

```# ? 2017 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net

def gcd(a, b):
while a != b:
if a > b:
a -= b
else:
b -= a
return a

num1 = int(input("Enter first number"))
num2 = int(input("Enter second number"))

print("GCD of", num1, "and", num2, "is equal to", gcd(num1, num2))```

#### Recursive version:

```# ? 2017 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net

def gcd(a, b):
if a > b:
return gcd(a - b, b)
elif a < b:
return gcd(a, b - a)
else:
return a

num1 = int(input("Enter first number"))
num2 = int(input("Enter second number"))

print("GCD of", num1, "and", num2, "is equal to", gcd(num1, num2))```

### Division-based version:

#### Iteration version:

```# ? 2017 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net

def gcd(a, b):
while(b != 0):
t = b
b = a % b
a = t
return a

num1 = int(input("Enter first number"))
num2 = int(input("Enter second number"))

print("GCD of", num1, "and", num2, "is equal to", gcd(num1, num2))```

#### Recursive version:

```# ? 2017 TheFlyingKeyboard and released under MIT License
# theflyingkeyboard.net

def gcd(a, b):
if b == 0:
return a;
else:
return gcd(b, a % b);

num1 = int(input("Enter first number"))
num2 = int(input("Enter second number"))

print("GCD of", num1, "and", num2, "is equal to", gcd(num1, num2))```

Python Euclidean Algorithm
Tagged on:

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close