Greatest Common Divisor

Write a Python program that finds the greatest common divisor (GCD) of two numbers input by the user.

Example 1:

Input: 60, 48 

Output: 12

Example 2:

Input: 101, 103 

Output: 1

The GCD of two numbers is the largest number that divides both of them without leaving a remainder. You can start from the smallest of the two numbers and keep reducing the number until you find a number that perfectly divides both numbers.

def compute_gcd(x, y):
    gcd = 1
    if x % y == 0:
        return y
    for k in range(int(y / 2), 0, -1):
        if x % k == 0 and y % k == 0:
            gcd = k
            break
    return gcd

print(compute_gcd(60, 48))

NOTE Owing to browser caching, any code input into the Trinket IDE might carry over across page refreshes or when transitioning between different questions. To commence with a clean slate, either click on the 'Reset Button' found within the IDE's Hamburger icon (☰) menu or resort to using Chrome's Incognito Mode.

Greatest Common Divisor

LOGIN