Hello Everyone,

LCM (Least Common Multiple) of two numbers is the smallest number which can be divided by both numbers.

For example, LCM of 15 and 20 is 60, and LCM of 5 and 7 is 35.

An **efficient solution** is based on the below formula for LCM of two numbers ‘a’ and ‘b’.

a x b = LCM(a, b) * GCD (a, b) LCM(a, b) = (a x b) / GCD(a, b)

Below is the implementation of the above idea:

`// C++ program to find LCM of two numbers`

`#include <iostream>`

`using`

`namespace`

`std;`

`// Recursive function to return gcd of a and b`

`long`

`long`

`gcd(`

`long`

`long`

`int`

`a, `

`long`

`long`

`int`

`b)`

`{`

` `

`if`

`(b == 0)`

` `

`return`

`a;`

` `

`return`

`gcd(b, a % b);`

`}`

`// Function to return LCM of two numbers`

`long`

`long`

`lcm(`

`int`

`a, `

`int`

`b)`

`{`

` `

`return`

`(a / gcd(a, b)) * b;`

`}`

` `

`// Driver program to test above function`

`int`

`main()`

`{`

` `

`int`

`a = 15, b = 20;`

` `

`cout <<`

`"LCM of "`

`<< a << `

`" and "`

` `

`<< b << `

`" is "`

`<< lcm(a, b);`

` `

`return`

`0;`

`}`

**Output**

LCM of 15 and 20 is 60

Note:

In arithmetic and number theory, the **least common multiple** , **lowest common multiple** , or **smallest common multiple** of two integers *a* and *b* , usually denoted by **lcm( a , b )** , is the smallest positive integer that is divisible by both

*a*and

*b*Since division of integers by zero is undefined, this definition has meaning only if

*a*and

*b*are both different from zero. However, some authors define lcm(

*a*,0) as 0 for all

*a*, which is the result of taking the lcm to be the least upper bound in the lattice of divisibility.

The lcm is the “lowest common denominator” (lcd) that can be used before fractions can be added, subtracted or compared. The lcm of more than two integers is also well-defined: it is the smallest positive integer that is divisible by each of them.

A multiple of a number is the product of that number and an integer. For example, 10 is a multiple of 5 because 5 × 2 = 10, so 10 is divisible by 5 and 2. Because 10 is the smallest positive integer that is divisible by both 5 and 2, it is the least common multiple of 5 and 2. By the same principle, 10 is the least common multiple of −5 and −2 as well.

The least common multiple of two integers *a* and *b* is denoted as lcm( *a* , *b* ). Some older textbooks use [ *a* , *b* ], uses `a*.b`

.

Example:

{lcm} (4,6)

Multiples of 4 are:

4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,…

Multiples of 6 are:

6,12,18,24,30,36,42,48,54,60,66,72,…

*Common multiples* of 4 and 6 are the numbers that are in both lists:

12,24,36,48,60,72,…

In this list, the smallest number is 12. Hence, the *least common multiple* is 12.