C++: Least Common Multiple

Compute the least common multiple of two integers.

Given m and n, the least common multiple is the smallest positive integer that has both m and n as factors. For example, the least common multiple of 12 and 18 is 36, because 12 is a factor (12 × 3 = 36), and 18 is a factor (18 × 2 = 36), and there is no positive integer less than 36 that has both factors. As a special case, if either m or n is zero, then the least common multiple is zero.

One way to calculate the least common multiple is to iterate all the multiples of m, until you find one that is also a multiple of n.

If you already have gcd for greatest common divisor, then this formula calculates lcm.

One can also find lcm by merging the prime decompositions of both m and n.

#include <boost/math/common_factor.hpp>
#include <iostream>
 
int main( ) {
   std::cout << "The least common multiple of 12 and 18 is " << 
      boost::math::lcm( 12 , 18 ) << " ,\n"
      << "and the greatest common divisor " << boost::math::gcd( 12 , 18 ) << " !" << std::endl ;
   return 0 ;
}

The least common multiple of 12 and 18 is 36 ,
and the greatest common divisor 6 !

SOURCE

Content is available under GNU Free Documentation License 1.2.