Single loop: Greatest Common Divisor (GCD)

Problem: Compute GCD (Greatest Common Divisor) of 2 positive integers.

Example:


GCD(45,30) = 15
GCD(10,7) = 1
GCD(12,10) = 2

Solution in Python:


def gcd(n0, m0):
    """
    Author: Mayur P Srivastava

    """

    assert n0 > 0
    assert m0 > 0

    if n0 < m0:
        print "GCD(%d,%d) = %d" % (n0, m0, gcd2(m0, n0))
    else:
        print "GCD(%d,%d) = %d" % (n0, m0, gcd2(n0, m0))


def gcd2(n, m):
    while m != 0:
        r = n % m
        n = m
        m = r
    return n

Concepts learned: Single loop.