Calculate and get the greatest common divisor and least common multiple in Python

Money and Business

The following is a description of how to calculate and obtain the greatest common divisor and least common multiple in Python.

  • The greatest common divisor and least common multiple of two integers
  • The greatest common divisor and least common multiple of three or more integers

Note that the specifications of functions provided in the standard library differ depending on the Python version. An example implementation of a function that is not in the standard library is also shown in this article.

  • Python 3.4 or earlier
    • GCD:fractions.gcd()(only two arguments)
  • Python 3.5 or later
    • GCD:math.gcd()(only two arguments)
  • Python 3.9 or later
    • GCD:math.gcd()(supports more than three arguments)
    • least common denominator:math.lcm()(supports more than three arguments)

Here we explain the method using the standard Python library; NumPy can easily be used to calculate the greatest common divisor and least common multiple for each element of multiple arrays.

The greatest common divisor and least common multiple of two integers

GCD

Since Python 3.5, there is a gcd() function in the math module. gcd() is an acronym for

  • greatest common divisor

Returns the greatest common divisor of the integer specified in the argument.

import math

print(math.gcd(6, 4))
# 2

Note that in Python 3.4 and earlier, the gcd() function is in the fractions module, not the math module. fractions must be imported and fractions.gcd().

least common denominator

The lcm() function, which returns the least common multiple, was added to the math module in Python 3.9. lcm is an acronym for

  • least common multiple

Returns the least common multiple of the integer specified in the argument.

print(math.lcm(6, 4))
# 12

Prior to Python 3.8, lcm() is not provided, but can be easily calculated using gcd().

lcm(a, b) = a * b / gcd(a, b)

Implementation Example.

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

/Since this results in a decimal float, two backslashes are used to truncate the decimal point and return an integer division result. Note that no processing is done to determine whether the argument is an integer or not.

The greatest common divisor and least common multiple of three or more integers

Python 3.9 or later

Starting with Python 3.9, all of the following functions support more than three arguments.

  • math.gcd()
  • math.lcm()
print(math.gcd(27, 18, 9))
# 9

print(math.gcd(27, 18, 9, 3))
# 3

print(math.lcm(27, 9, 3))
# 27

print(math.lcm(27, 18, 9, 3))
# 54

*If you want to calculate the greatest common divisor or least common multiple of the elements of a list, specify the argument with this.

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 or earlier

Prior to Python 3.8, the gcd() function supported only two arguments.

To find the greatest common divisor or least common multiple of three or more integers, no particularly complicated algorithm is required; just calculate the greatest common divisor or least common multiple for each of the multiple values in turn using the higher-order function reduce().

GCD

from functools import reduce

def my_gcd(*numbers):
    return reduce(math.gcd, numbers)

print(my_gcd(27, 18, 9))
# 9

print(my_gcd(27, 18, 9, 3))
# 3

l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3

Again, note that before Python 3.4, the gcd() function is in the fraction module, not the math module.

least common denominator

def my_lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def my_lcm(*numbers):
    return reduce(my_lcm_base, numbers, 1)

print(my_lcm(27, 9, 3))
# 27

print(my_lcm(27, 18, 9, 3))
# 54

l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54
Copied title and URL