Calculate the Least Common Multiple of Two Integers | Code Samurai

Calculate the Least Common Multiple of Two Integers | Code Samurai

Calculate the Least Common Multiple of Two Integers

Question: write an algorithm to return the least common multiple (LCM) of two integers. For example, if the inputs are 3 and 4, the function returns 12.

Solution: least common multiple (LCM) is the lowest value that is a multiple of both integers. That means LCM is divisible by both integers or the modulus of LCM divided by either integers is 0 (LCM % num = 0). Thus, we just need to start with a reasonable number and keep increasing that number until it is divisible by both integers. The number is then the LCM of the integers.

But where is the reasonable number to start out? Well, instead of starting out at 1, we can start out at the highest integer between the two integers. The reason is that a number that is less than either of those two integers can't be divisible by those integers. For example, if we are to find LCM of 2 and 3, then any number that is less than 3 is surely not the LCM. Thus, we can safely start our search at 3. Notice that one integer can be the LCM of another integer. That's why we start out at the higher number. For example, the LCM of 2 and 4 is 4. Here is the algorithm in C:

Read full article from Calculate the Least Common Multiple of Two Integers | Code Samurai