Super Simple Python is a series of Python projects you can do in under 15 minutes. In this episode, we’ll be covering two ways to get the Greatest Common Denominator (GCD) of two numbers in just 3 lines of Python each!

We’ve covered a lot of different kinds of programs in the Super Simple Python series. We’ve covered programs using the random library like the Dice Roll Simulator, infrastructural programs like the Card Deck Generator, and math programs like the Prime Factorizer. This one falls in the math category.

Watch the video here:

Euclidean Algorithm

Euclid is a famous Greek mathematician. He came up with countless numbers of math theories, including the Euclidean Algorithm. The Euclidean Algorithm is a simple way to find the Greatest Common Denominator of two integers. Given two integers, we subtract the smaller from the larger until one of the numbers is equal to 0. The remaining positive integer is the Greatest Common Denominator. Let’s take a look at the Euclidean Algorithm in practice.

Iterative Implementation in Python

The first implementation of the Euclidean Algorithm in Python that we’ll take a look at is how to iteratively get the GCD of two numbers. This function will take two integers, x, and y, and return the Greatest Common Denominator. It doesn’t matter if you pick x or y for the condition in the while loop, for this example, we’ll pick y. While y is not yet 0, we’ll set the new values of x and y to y and the remainder when x is divided by y. At the end of the loop, y will be 0, and we return x as the GCD.

def iterative_gcd(x: int, y: int):
    while(y):
        x, y = y, x%y
    return x

Recursive Implementation in Python

The second implementation of the Euclidean Algorithm in Python we’ll implement is the recursive implementation. Looking at the iterative function above, it looks like it does the same thing every single step right? That’s a surefire sign that there is a way to recursively implement this function. Just like our iterative function, our recursive function will take two integers, x and y, as input. 

In this case, we’ll build in an if statement to stop the recursion when one of the numbers is equal to 0. Once again, we choose y arbitrarily. We swapped x and y with y and the remainder when x is divided by y in the iterative version. In the recursive version, we’ll just return the function when the inputs x and y are swapped with y and the remainder when x is divided by y.

def recursive_gcd(x: int, y: int):
    if y == 0:
        return x
    return recursive_gcd(y, x%y)

Testing

Now let’s take a look at some examples of our implementations. I’ve written 5 examples that we’ll test with both implementations. I’ve also commented the expected output next to them.

print(iterative_gcd(10, 20)) # 10
print(iterative_gcd(33, 41)) # 1
print(iterative_gcd(48, 64)) # 16
print(iterative_gcd(99, 81)) # 9
print(iterative_gcd(210, 70)) # 70
 
print(recursive_gcd(10, 20)) # 10
print(recursive_gcd(33, 41)) # 1
print(recursive_gcd(48, 64)) # 16
print(recursive_gcd(99, 81)) # 9
print(recursive_gcd(210, 70)) # 70

When we run our program we should see something like the following image. Just like we expected.

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.