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 no intermediate value exceeds the answer. For 4 and 6 , the gcd is 2 , and 4 / 2 × 6 = 12 .

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

With the gcd formula it is O(log(min(a, b))) time, the cost of Euclid's algorithm, and O(1) space. Stepping through multiples of the larger number is O(min(a, b)) , and counting by one is O(lcm(a, b)) .

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 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.

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.

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 tied by one fact: gcd(a, b) × lcm(a, b) = a × b. So the fast answer is a × b / gcd(a, b). The product can reach 10^12 and overflow a 32-bit integer even when the answer fits, so 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 at least the larger number. Start m at max(a, b) and add 1 until both numbers divide it; you try candidates in increasing order, so the first hit is the least. For 4 and 6 you try 6 through 11 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 the primes 46337 and 46327 the answer is 2146654199, over two billion tries.

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

The answer must be a multiple of the larger number, big, so jump through big, 2 × big, 3 × big and stop at the first one the smaller number divides. For 4 and 6 you try 6, then 12.

Since small × big is always a common multiple, the loop runs at most min(a, b) times, at most a million here. That is fast enough for these limits, 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. For each prime, the gcd takes the smaller of its two powers and the lcm the larger, so together they use every factor of a and of b exactly once: gcd × lcm = a × b. For 4 = 2² and 6 = 2 × 3, the gcd is 2 and the lcm is 2² × 3 = 12.

Euclid's algorithm finds the gcd in O(log(min(a, b))) steps. Then compute a / gcd × b in that order: the gcd divides a exactly, so nothing is lost, and no step exceeds the answer. a × b / gcd overflows a 32-bit integer on a = b = 10^6, where the product is 10^12 and the answer 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

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 comes out wrong or negative (a Rust debug build panics), even though the lcm fits.
Dividing 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. Afterwards they hold the gcd and 0, so work on copies.
Assuming the answer is a × b. That holds only when the numbers share no factor: lcm(4, 6) is 12, not 24.

Frequently asked questions3

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 no intermediate value exceeds the answer. For 4 and 6, the gcd is 2, and 4 / 2 × 6 = 12.

What is the time complexity of computing the LCM?

With the gcd formula it is O(log(min(a, b))) time, the cost of Euclid's algorithm, and O(1) space. Stepping through multiples of the larger number is O(min(a, b)), and counting by one is O(lcm(a, b)).

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 use 64-bit integers when the list is long.