Greatest Common Divisor

Tags: For loop, GCD, Math

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
    return gcd

print(compute_gcd(60, 48))

© Let’s Data Science


Unlock AI & Data Science treasures. Log in!