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