Euclidean Algorithm implementation written in Python.

Subtraction-based version:

Iteration version:

# © 2017 TheFlyingKeyboard
# 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
# 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
# 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
# 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:     

Leave a Reply

Your email address will not be published. Required fields are marked *