Describe an algorithm to compute the least common multiple (lcm) of two numbers.
The World of Algorithms · Question 7 of 15
Describe an algorithm to compute the least common multiple (lcm) of two numbers.
The lcm of and is the smallest number that is a multiple of both. The multiples of are , so we check them in increasing order and stop at the first one that divides.
Algorithm to find lcm(m, n)
-
Set to 1.
-
If divides , report as lcm(m, n) and stop.
-
Otherwise, increase by 1 and repeat Step 2.
The algorithm always stops: when , the number is a multiple of both, so we never go beyond . Since we check the multiples of in increasing order, the first common multiple we meet is the least one. (It is quicker to take as the larger of the two numbers, so fewer multiples are checked.)
Example 1: lcm(18, 12), with , .
-
: 18; 12 does not divide 18.
-
: 36; 12 divides 36. Report lcm(18, 12) = 36.
Example 2: lcm(825, 375), with , . The multiples of 825 are 825, 1650, 2475, 3300, 4125. 375 does not divide the first four, but . So lcm(825, 375) = 4125.
Another way, using a gcd algorithm from this chapter: compute and report . For example, , so
which agrees with Example 2.
