Program to Find the Least Common Multiple (LCM) in C

Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers. For example, the LCM of 12 and 18 is 36.

We will explore three different methods to find the LCM of two numbers using C programming.

Method 1: Using HCF

The LCM of two numbers can be calculated using the formula:

LCM(a, b) = (a * b) / HCF(a, b)

#include <stdio.h>

int findHCF(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int findLCM(int a, int b) {
    return (a * b) / findHCF(a, b);
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("LCM of %d and %d is %d", num1, num2, findLCM(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 12 18
LCM of 12 and 18 is 36

Method 2: Using Iteration

We start from the maximum of the two numbers and keep increasing until we find a number that is divisible by both.

#include <stdio.h>

int findLCMIterative(int a, int b) {
    int max = (a > b) ? a : b;
    while (1) {
        if (max % a == 0 && max % b == 0)
            return max;
        max++;
    }
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("LCM of %d and %d is %d", num1, num2, findLCMIterative(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 12 18
LCM of 12 and 18 is 36

Method 3: Using Recursion

We use recursion to find the LCM by incrementing multiples of the larger number until we find a common multiple.

#include <stdio.h>

int findLCMRecursive(int a, int b, int multiple) {
    if (multiple % a == 0 && multiple % b == 0)
        return multiple;
    return findLCMRecursive(a, b, multiple + 1);
}

int findLCM(int a, int b) {
    int max = (a > b) ? a : b;
    return findLCMRecursive(a, b, max);
}

int main() {
    int num1, num2;
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);
    
    printf("LCM of %d and %d is %d", num1, num2, findLCM(num1, num2));
    return 0;
}
            

Output:

Enter two numbers: 12 18
LCM of 12 and 18 is 36