The least common multiple of the Python code implementation list

  • 2021-12-12 09:18:03
  • OfStack

Directory 1. lcm2. functools. reduce3. Actual use

The code snippet read in this article comes from 30-seconds-of-python (

1. lcm

from functools import reduce
from math import gcd

def lcm(numbers):
  return reduce((lambda x, y: int(x * y / gcd(x, y))), numbers)

lcm([12, 7]) # 84
lcm([1, 3, 4, 5]) # 60

The greatest common divisor and the least common multiple of two numbers satisfy the following formula:

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

For a list of more than two data, you only need to continue to calculate the least common multiple of any two numbers and the rest of the other numbers.

That is to say:

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

So we use functools.reduce Function to iterate over the list.

2. functools.reduce

functools.reduce(function, iterable[, initializer])

reduce The first argument in the function is the function function Which takes two parameters. reduce Function sets the function The cumulative application is in the second parameter, iterable On an object that can be iterated. function Take the first two values of the iterable object as input parameters, and take the return value and the next 1 value of the iterable object as function Performs the next iteration until all the values of the iterable object are exhausted. For example, the following example:

# ((((1+2)+3)+4)+5)
reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])

The reduce function is roughly equivalent to:

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
        value = initializer
    for element in it:
        value = function(value, element)
    return value

3. Practical use

The above code snippet shows the lcm(a, b, c, ...) = lcm(lcm(a, b), c, ...)0 1 method of use. Careful students can see that if they want to put into practical production and application, lcm Function is a number of problems, mainly two points, 1 is exception handling, including zero division; The other one is that the least common multiple is a positive integer, and the return value of this function may be negative.

The code of 30-seconds-of-python ( mainly shows one idea. Edge situations and exceptions are not checked for. The reason behind this is to keep the project simple and show interesting techniques and ways of thinking. All code snippets assume that the user has a basic understanding of the problem, language, and potential errors that can occur, so no exception handling or parameter checking is added.

Related articles: