Categories
General Python python starter projects

Super Simple Python: Two Ways to Get GCD

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.

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

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.

Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly