Question

IN PYTHON

Write a recursive function for Euclid's algorithm to find the greatest common divisor (gcd) of two positive integers. gcd is the largest integer that divides evenly into both of them. For example, the gcd(102, 68) = 34. You may recall learning about the greatest common divisor when you learned to reduce fractions. For example, we can simplify 68/102 to 2/3 by dividing both numerator and denominator by 34, their gcd. Finding the gcd of huge numbers is an important problem that arises in many commercial applications. We can efficiently compute the gcd using the following property, which holds for positive integers p and q:

          If p > q, the gcd of p and q is the same as the gcd of q and p % q.

Answer 1

def gcd(m, n):
    if m < n:
        return gcd(n, m)
    elif n == 0:
        return m
    else:
        return gcd(n, m % n)


n1 = int(input("Enter an integer: "))
n2 = int(input("Enter another integer: "))
print("GCD(" + str(n1) + ", " + str(n2) + ") is " + str(gcd(n1, n2)))