The Way of the Serpent

Pythonic Tips & Tricks — Finding the GCD and LCM

How to get the Greatest Common Denominator and Least Common Multipliers using Python

Photo by 浮萍 闪电 on Unsplash

For a lot of us, finding the greatest common denominator between numbers was a common exercise in grade school math. However, in the real world finding GCDs can form an integral part of our algorithms and analysis. In this article we shall go over how to get GCDs under different scenarios.

Let’s begin!

“Create a function that will take two integers as inputs and find their Greatest Common Denominator.”

Sounds simple enough, let’s see a typical algorithm that find the GCD of two integers. A common algorithm is the one below:

def get_gcd_1(num1, num2):
    while num1 != num2: 
        if num1 > num2:
            num1 = num1 - num2
        else:
            num2 = num2 - num1
    return num1
print(get_gcd_1(25, 5))
print(get_gcd_1(5, 20))
print(get_gcd_1(30, 10))
print(get_gcd_1(1500, 75))
print(get_gcd_1(20, 35))

Figure 1. First GCD Function

This is a fairly straightforward algorithm and does give us the GCD. However, there are better ways and more efficient ways to structure the algorithm. For starters let’s see how many iterations it takes for the algorithm to find the GCD.

def get_gcd_1(num1, num2):
    while num1 != num2: 
        if num1 > num2:
            num1 = num1 - num2
        else:
            num2 = num2 - num1
        print(num1, num2)
    return num1
print(get_gcd_1(1500, 75))

Figure 2. Iterations until GCD is found

We can see that the algorithm will go through 20 iterations before the GCD is found. If we were to run this algorithm over a much larger dataset then high number of iterations would definitely be an issue.

Instead, let us try a much simpler algorithm.

def get_gcd_2(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    return num1
print(get_gcd_2(25, 5))
print(get_gcd_2(5, 20))
print(get_gcd_2(30, 10))
print(get_gcd_2(1500, 75))
print(get_gcd_2(20, 35))

Figure 3. Second GCD Function

The second function is significantly cleaner than the first. We also make use of the % or modular operator. What it does is essentially return the remained between two numbers. If the first number is perfectly divisible by the second number then the operation will return 0.

print(10 % 5)
print(20 % 7)
print(100 % 99)
print(1000 % 10)
print(25 % 6)

Figure 4. Sample of Modular Operator

Now let us check how many iterations our second GCD Function has to go through before it returns the GCD.

def get_gcd_2(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
        print(num1, num2)
    return num1
print(get_gcd_2(1500, 75))

Figure 5. Iterations until GCD is found

Amazing! We can see that this algorithm will get us the GCD in only 2 iterations. This is much more efficient than our first function. We can actually make one more improvement to our function. The line num2 != 0 is actually superfluous. We can shorten it to simply while (num2). Our resulting function will then be as follows.

def get_gcd_2(num1, num2):
    while (num2):
        num1, num2 = num2, num1 % num2
        print(num1, num2)
    return num1
print(get_gcd_2(1500, 75))

Figure 6. Shortened Function

Excellent, we have found a pretty efficient algorithm to allow us to search for the GCD. From here we can actually find the Least Common Multiplier (LCM).

“Create a function that will take two integers as inputs and find their Least Common Multiplier.”

Put simply, the Least Common Multiplier is the smallest number that is evenly divisible by two or more numbers. To construct a function that can search for it we can make use of our GCD function.

def get_lcm(num1, num2):
    return (num1*num2)/ get_gcd_2(num1,num2)
print(get_lcm(1500, 75))
print(get_lcm(117 , 33))
print(get_lcm(56, 5))

Figure 7. Least Common Multiples Function

We can see that the Least Common Multiple function is able to retrieve the correct numbers. Now let us generalize our functions so that they will be able to work with any quantity of numbers.

“Create a function that will take a list of integers as inputs and find their Greatest Common Denominator and their Least Common Multiplier.”

To be able to do this we must import the reduce function from the functools library.

from functools import reduce
def get_gcd_lcm(list_of_ints):
    help_func = lambda x,y : x if y == 0 else g(y, x % y)  
    gcd = reduce(lambda x,y : help_func(x,y), list_of_ints)
    lcm = reduce((lambda x, y: x * y), list_of_ints) / gcd
    return gcd, lcm
    
results = get_gcd_lcm([75,1500,25,50,100])
print(f'GCD : {results[0]} LCM : {results[1]}')

Figure 8. Generalized GCD and LCM Function

Nice, we were able to generate a function that can take a list and generate the GCD and LCM.

In Conclusion

In this article, we were able to successfully create functions to find the GCD and LCM of a list of integers. Both values are quite useful for data scientists as they allow us to get a better idea of the data we are handling. Though this article was rather general, in future articles we shall go over the many uses of these statistics and apply them to real world data. For now, I hope that you were able to find this information useful for your current task.