GCD and LCM

Finding the GCD
GCD for 60 and 40 is 20: 

60 = 40 * 1 + 20
40 = 20 * 2 + 0

LCM for 60 and 40 is 120:
60*40 / 20

Recursive solution for GCD

int gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

Iterative solution for GCD

int gcd(a, b):
    while (b != 0): //swap a with b, and b with a%b
        temp = a%b
        a = b
        b = t
    return a

Finding the LCM
Method1 : Using GCD

int lcm(a, b):
    return (a*b)/gcd(a, b)

Method 2:
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:

int lcm(int num1, int num2)
  {
    if (num1 % num2 == 0)
      return num1;

    if (num2 % num1 == 0)
      return num2;
      
    int n = (num1 <= num2) ? num2 : num1;
    
    for (; ; n++)
    {
      if(n % num1 == 0 && n % num2 == 0)
         return n;
    }
  }

Explanation: our function takes two integers as arguments and returns the LCM of those integers.

1. First, we take the modulus of the first integer (num1) and the second integer (num2). If num1 % num2 equals 0, we know num1 is the LCM because num1 is divisible by num1 and is the smallest number that is not less than num1 and num2. Similarly, if num2 % num1 equals 0 then num2 is the LCM.
2. When neither integer is the LCM, we find out which integer is greater and begin to find the LCM starting from that integer. That's exactly what the for loop does. For every iteration, we increase n by 1 until we find a number that divisible by both num1 and num2. This loop guarantees to find the solution. That's why we don't need any other return statement outside the loop. Nor we need a termination condition for the loop.