AlgoMaster Logo

LCM of Two Numbers

Last Updated: June 7, 2026

easy
4 min read

Understanding the Problem

A common multiple of two numbers is any value that both divide evenly. For 4 and 6, the multiples of 4 are 4, 8, 12, 16, 20, 24, ... and the multiples of 6 are 6, 12, 18, 24, .... The values that appear in both lists are 12, 24, 36, ..., and the smallest of them is 12. That smallest shared multiple is the least common multiple.

The least common multiple is never smaller than the larger input, and never larger than the product a * b, which is always divisible by both. The answer sits in that range.

Two properties guide the efficient solution. First, the least common multiple and the greatest common divisor are tied together by the identity gcd(a, b) * lcm(a, b) = a * b, so knowing one gives the other. Second, the greatest common divisor is fast to compute with the Euclidean algorithm. Together they give a method that runs in time proportional to the number of digits rather than the size of the answer.

Key Constraints:

  • a and b are positive → Every multiple under consideration is a positive integer, so the smallest common multiple is well defined and at least max(a, b).
  • The product a * b can grow large → For inputs near 10^4, the product reaches 10^8, which fits in a 32-bit int. Dividing by the greatest common divisor before multiplying keeps the intermediate value small and avoids overflow even when the inputs grow beyond this range.

Approach 1: Using the GCD Formula

Intuition

Why does gcd(a, b) * lcm(a, b) = a * b hold? The greatest common divisor counts each shared prime factor once, while the least common multiple raises each prime to the higher of its two powers. Multiplying them counts every prime factor as many times as it appears across both numbers combined, which is the count in a * b.

Rearranging the identity gives lcm(a, b) = a * b / gcd(a, b). Since the greatest common divisor divides a, compute a / gcd(a, b) exactly, then multiply by b. Writing it as a / gcd * b rather than a * b / gcd keeps the intermediate value smaller, because the full product a * b is never formed before dividing. The greatest common divisor comes from the Euclidean algorithm: replace (a, b) with (b, a mod b) repeatedly until the second value is 0, at which point the first value is the greatest common divisor.

Algorithm

  1. Compute g = gcd(a, b) using the Euclidean algorithm: while b is not 0, set (a, b) to (b, a mod b); the remaining value is the greatest common divisor.
  2. Divide one input by g first: compute a / g.
  3. Multiply that result by the other input: (a / g) * b. Use a 64-bit type for the multiplication if the inputs can be large.
  4. Return the product.

Example Walkthrough

Input:

12
a
18
b

Start by computing the greatest common divisor of 12 and 18. The Euclidean algorithm gives gcd(12, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6, since 18 mod 12 = 6 and 12 mod 6 = 0. Now apply the formula: divide a by the greatest common divisor first, 12 / 6 = 2, then multiply by b, 2 * 18 = 36. The least common multiple is 36. Checking against the definition, 36 is divisible by both 12 (36 / 12 = 3) and 18 (36 / 18 = 2), and no smaller positive value is.

36
result

Code

Approach 2: Brute Force by Multiples

Intuition

Search for the answer directly by walking through the multiples of one input and stopping at the first one the other input also divides.

Step through multiples of the larger input m = max(a, b), not the smaller one. The answer must be a multiple of both, so it is a multiple of m. Starting at m and incrementing by m, check m, 2m, 3m, ... and return the first value also divisible by the smaller input. Stepping by m rather than 1 skips every value that could not be the answer, since any common multiple has to be a multiple of m. This is slower than the greatest common divisor method because the number of steps grows with the size of the answer, but it makes the definition concrete.

Algorithm

  1. Let m = max(a, b) and n = min(a, b).
  2. Start a candidate at multiple = m.
  3. While multiple is not divisible by n, add m to multiple.
  4. Return multiple, the first multiple of m that n also divides.

Example Walkthrough

Input:

4
a
6
b

Here m = max(4, 6) = 6 and n = min(4, 6) = 4. The candidate starts at 6. Is 6 divisible by 4? No, 6 mod 4 = 2, so add 6 to get 12. Is 12 divisible by 4? Yes, 12 mod 4 = 0, so the search stops and returns 12. We checked only the multiples of 6, namely 6 and 12, and skipped every value in between, since none of them could be a common multiple.

12
result

Code