note.nkmk.me

Find GCD and LCM in Python: math.gcd(), lcm()

Modified: | Tags: Python, Mathematics

This article explains how to find the greatest common divisor (GCD) and least common multiple (LCM) in Python.

Contents

Note that the specifications of functions provided in the standard library differ depending on the Python version.

  • Python 3.4 or earlier
    • GCD: fractions.gcd() (Only supports two arguments)
  • Python 3.5 or later
    • GCD: math.gcd() (Only supports two arguments)
  • Python 3.9 or later
    • GCD: math.gcd() (Supports three or more arguments)
    • LCM: math.lcm() (Supports three or more arguments)

All sample code in this article assumes that the math module has been imported.

import math
source: gcd_lcm.py

GCD of two numbers

Python 3.5 or later: math.gcd()

The gcd() function was added to the math module in Python 3.5.

print(math.gcd(6, 4))
# 2
source: gcd_lcm.py

Python 3.4 or earlier: fractions.gcd()

Note that in Python 3.4 or earlier, the gcd() function is located in the fractions module, not the math module. Therefore, you need to import fractions and use fractions.gcd().

LCM of two numbers

Python 3.9 or later: math.lcm()

The lcm() function was added to the math module in Python 3.9.

print(math.lcm(6, 4))
# 12
source: gcd_lcm.py

Python 3.8 or earlier: Use GCD

In Python 3.8 or earlier, lcm() is not provided, but it can be calculated using gcd().

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

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

print(my_lcm(6, 4))
# 12
source: gcd_lcm.py

Note that the function provided in the example above does not check if the arguments are integers.

GCD and LCM of three or more numbers

Python 3.9 or later: math.gcd(), math.lcm()

In Python 3.9 or later, both math.gcd() and math.lcm() support an arbitrary number of arguments.

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
source: gcd_lcm_multi.py

If you want to find the GCD and LCM of the elements within a list, use * to unpack the list as arguments.

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

print(math.lcm(*l))
# 54
source: gcd_lcm_multi.py

Python 3.8 or earlier: Use functools.reduce()

In Python 3.8 or earlier, gcd() supports only two arguments.

To find the GCD and LCM of three or more integers, just calculate them cumulatively.

gcd(a, b, c, d, ...) = gcd( ... gcd(gcd(gcd(a, b), c), d), ...)
lcm(a, b, c, d, ...) = lcm( ... lcm(lcm(lcm(a, b), c), d), ...)

Use the reduce() function of the functools module.

GCD

import functools

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

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
source: gcd_lcm_multi.py

LCM

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

def my_lcm(*integers):
    return functools.reduce(my_lcm_base, integers)

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
source: gcd_lcm_multi.py

Without arguments

When called without arguments, math.gcd() returns 0, and math.lcm() returns 1.

print(math.gcd())
# 0

print(math.lcm())
# 1
source: gcd_lcm_multi.py

The functions defined above raise an error without arguments.

# print(my_gcd())
# TypeError: reduce() of empty iterable with no initial value

# print(my_lcm())
# TypeError: reduce() of empty iterable with no initial value
source: gcd_lcm_multi.py

To get the same result as math.gcd() and math.lcm(), specify the third argument initializer of reduce().

def my_gcd_init(*integers):
    return functools.reduce(math.gcd, integers, 0)

print(my_gcd_init())
# 0

print(my_gcd_init(27, 18, 9, 3))
# 3
source: gcd_lcm_multi.py
def my_lcm_init(*integers):
    return functools.reduce(my_lcm_base, integers, 1)

print(my_lcm_init())
# 1

print(my_lcm_init(27, 18, 9, 3))
# 54
source: gcd_lcm_multi.py

Related Categories

Related Articles