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