The least common multiple of the Python code implementation list
- 2021-12-12 09:18:03
- OfStack
The code snippet read in this article comes from 30-seconds-of-python (https://github.com/30-seconds...).
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)
# EXAMPLES
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)
else:
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 (https://github.com/30-seconds...) 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.