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 <iostream>
using namespace std;

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;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "LCM of " << num1 << " and " << num2 << " is " << findLCM(num1, num2);
    return 0;
}
            

Output:

Enter first number: 12
Enter second number: 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 <iostream>
using namespace std;

int findLCM(int a, int b) {
    int maxNum = max(a, b);
    while (true) {
        if (maxNum % a == 0 && maxNum % b == 0) {
            return maxNum;
        }
        maxNum++;
    }
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "LCM of " << num1 << " and " << num2 << " is " << findLCM(num1, num2);
    return 0;
}
            

Output:

Enter first number: 12
Enter second number: 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 <iostream>
using namespace std;

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) {
    return findLCMRecursive(a, b, max(a, b));
}

int main() {
    int num1, num2;
    cout << "Enter first number: ";
    cin >> num1;
    cout << "Enter second number: ";
    cin >> num2;
    
    cout << "LCM of " << num1 << " and " << num2 << " is " << findLCM(num1, num2);
    return 0;
}
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36