Oleksii Trekhleb | Javascript algorithms (Least common multiple)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 2 phút đọc.
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0)as 0 for all a, which is the result of taking the lcm to be the least upper bound in the lattice of divisibility.
Example
What is the LCM of 4 and 6?
Multiples of 4 are:
4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76…
and the multiples of 6 are:
6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72…
Common multiples of 4 and 6 are simply the numbers that are in both lists:
12, 24, 36, 48, 60, 72…
So, from this list of the first few common multiples of the numbers 4 and 6, their least common multiple is 12.
Computing the least common multiple
The following formula reduces the problem of computing the least common multiple to the problem of computing the greatest common divisor (GCD), also known as the greatest common factor:
lcm(a, b) = |a b| / gcd(a, b)
A Venn diagram showing the least common multiples of combinations of 2, 3, 4, 5 and 7 (6 is skipped as it is 2 × 3, both of which are already represented).
For example, a card game which requires its cards to be divided equally among up to 5 players requires at least 60 cards, the number at the intersection of the 2, 3, 4 and 5 sets, but not the 7 set.
