Least common multiple

O(a·b / gcd(a,b))

The least common multiple (LCM) of two integers a and b is the smallest positive integer that is divisible by both. One direct approach is to enumerate multiples of the larger number (m, 2m, 3m, …) and stop at the first multiple that is also divisible by the smaller. This requires at most smaller/gcd(a,b) steps, since lcm(a,b) = larger · (smaller / gcd(a,b)). The LCM is fundamental in arithmetic: adding fractions, scheduling repeating events, and finding periods in modular arithmetic all rely on it.

Sequence
Press ▶ to run
Edit the input and press Play

How it works

  1. Choose the larger value m and the smaller value s
  2. Enumerate multiples k·m for k = 1, 2, 3, …
  3. Check whether each multiple is divisible by s
  4. The first multiple that passes is lcm(a, b)

Pseudocode

1lcm(a, b):                           # O(b / gcd(a,b)) where b = larger2  m = max(a, b);  s = min(a, b)3  for k = 1, 2, 3, ...:4    if (k * m) % s == 0:5      return k * m              # found lcm