Least Common Multiple

Q: What is the formula for the LCM of two numbers?

lcm(a, b) = a × b / gcd(a, b) , computed as a / gcd(a, b) × b so the intermediate value never exceeds the answer. For 4 and 6 , the gcd is 2 , and 4 / 2 × 6 = 12 .

Q: Why is gcd(a, b) × lcm(a, b) equal to a × b?

For each prime, the gcd uses the smaller of its powers in a and b , and the lcm uses the larger one. Smaller plus larger is the sum of both powers, which is exactly that prime's power in a × b . Every prime matches, so the two products are equal.

Q: What is the time complexity of computing the LCM?

With the gcd formula it is O(log(min(a, b))) , the cost of Euclid's algorithm, plus one division and one multiplication. It needs O(1) extra space. Searching through multiples is much slower: O(min(a, b)) when you step by the larger number, and O(lcm(a, b)) when you count by one.

Q: How do you find the LCM of more than two numbers?

Fold the list: lcm(a, b, c) = lcm(lcm(a, b), c) . For [4, 6, 10] , lcm(4, 6) = 12 and lcm(12, 10) = 60 . The running value grows quickly, so watch for overflow and use 64-bit integers when the list is long.

BeginnerMath and simulation

+10

You get two positive integers a and b. Return their least common multiple: the smallest positive integer that both a and b divide with no remainder.

For example, the multiples of 6 are 6, 12, 18, 24 and so on, the multiples of 8 are 8, 16, 24 and so on, and the first number on both lists is 24.

Function

lcm(a: integer, b: integer) → integer

ainteger: the first positive integer
binteger: the second positive integer
Returnsinteger: the smallest positive integer that is a multiple of both a and b

Constraints

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
The answer fits in a signed 32-bit integer: lcm(a, b) ≤ 2³¹-1. The product a × b may not.

Examples

Input: a = 4b = 6
Output: 12
Explanation: The multiples of 6 start 6, 12, 18; the multiples of 4 start 4, 8, 12. The first number on both lists is 12.

Input: a = 7b = 3
Output: 21
Explanation: 7 and 3 share no factor other than 1, so their least common multiple is their product, 21.

Input: a = 15b = 45
Output: 45
Explanation: 15 divides 45 exactly, so 45 is already a multiple of both, and no smaller multiple of 45 exists.

+15 hidden tests on Submit

Follow-up

Can you find the gcd with no division or remainder at all, using only subtraction and halving?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The least common multiple and the greatest common divisor are two sides of one fact: gcd(a, b) × lcm(a, b) = a × b. So the fast answer is a × b / gcd(a, b), with one catch. The product can reach 10^12, which overflows a 32-bit integer even when the answer fits, so you divide by the gcd before you multiply.

Count up from the larger number

Correct, but does not finish on the largest tests

Intuition

The answer is a multiple of both numbers, so it is at least as large as the larger of them. Start a candidate m at max(a, b) and add 1 until both a and b divide it. You try the candidates in increasing order, so the first one that works is the least.

For 4 and 6 you try 6, 7, 8, 9, 10 and 11, which fail, and stop at 12. The loop always ends, because a × b is a common multiple.

The number of tries is about the size of the answer. For 46337 and 46327, two primes, the answer is 2146654199, so the loop runs over two billion times. That is far too slow.

Algorithm

Set m to the larger of a and b.
While m % a or m % b is not 0, add 1 to m.
Return m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Step through multiples of the larger number

Intuition

Most of the candidates in the count are hopeless: the answer has to be a multiple of the larger number, call it big. So jump straight from one multiple of big to the next, big, 2 × big, 3 × big, and stop at the first one the smaller number divides.

For 4 and 6 you try 6 (4 does not divide it) and then 12 (it does). The answer is k × big for some k, and k is at most the smaller number, because small × big is always a common multiple. So the loop runs at most min(a, b) times, which is never more than a million here.

That is fast enough here, but it still grows with the input. With numbers up to 10^18 it would not be.

Algorithm

Let big be the larger number and small the smaller one.
Set m = big.
While m % small is not 0, add big to m.
Return m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Divide by the gcd, then multiply

Intuition

Split both numbers into prime factors. The gcd takes each prime with the smaller of its two powers, the lcm takes the larger one, and together they use every factor of a and of b exactly once. That gives gcd(a, b) × lcm(a, b) = a × b, so lcm(a, b) = a × b / gcd(a, b). For 4 = 2² and 6 = 2 × 3, the gcd is 2 and the lcm is 2² × 3 = 12.

Find the gcd with Euclid's algorithm: replace (x, y) with (y, x % y) until y is 0. That takes O(log(min(a, b))) steps.

Then compute a / gcd × b, in that order. The gcd divides a exactly, so the division loses nothing, and the result never exceeds the answer. Writing a × b / gcd instead overflows a 32-bit integer on a = b = 10^6: the product is 10^12, while the answer is only 10^6.

Algorithm

Copy a and b into x and y.
While y is not 0, replace (x, y) with (y, x % y). Now x is the gcd.
Divide a by x.
Multiply the result by b and return it.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Pitfalls and edge cases

The formula is one line, and the bugs are in the order of the arithmetic.

Computing a × b first. In Java, C, C++, C# and Rust the product of two numbers near 10^6 overflows a 32-bit integer and the answer comes out wrong or negative (a Rust debug build panics instead), even though the true lcm fits.
Dividing a × b by the gcd in floating point. The result can come back as 2.146654199E9 or lose its last digits; keep everything in integers.
Running Euclid's loop on a and b themselves and then using them in the formula. After the loop they hold the gcd and 0, so work on copies.
Assuming the answer is a × b. That holds only when the two numbers share no factor: lcm(4, 6) is 12, not 24.

Frequently asked questions4

What is the formula for the LCM of two numbers?

lcm(a, b) = a × b / gcd(a, b), computed as a / gcd(a, b) × b so the intermediate value never exceeds the answer. For 4 and 6, the gcd is 2, and 4 / 2 × 6 = 12.

Why is gcd(a, b) × lcm(a, b) equal to a × b?

For each prime, the gcd uses the smaller of its powers in a and b, and the lcm uses the larger one. Smaller plus larger is the sum of both powers, which is exactly that prime's power in a × b. Every prime matches, so the two products are equal.

What is the time complexity of computing the LCM?

With the gcd formula it is O(log(min(a, b))), the cost of Euclid's algorithm, plus one division and one multiplication. It needs O(1) extra space. Searching through multiples is much slower: O(min(a, b)) when you step by the larger number, and O(lcm(a, b)) when you count by one.

How do you find the LCM of more than two numbers?

Fold the list: lcm(a, b, c) = lcm(lcm(a, b), c). For [4, 6, 10], lcm(4, 6) = 12 and lcm(12, 10) = 60. The running value grows quickly, so watch for overflow and use 64-bit integers when the list is long.