C++ Program to Find LCM of Two Numbers

To find the LCM of two numbers in C++, use the formula lcm = (a / gcd(a, b)) * b where gcd is the greatest common divisor; you can compute gcd using the Euclidean algorithm and then calculate LCM.

Examples

Inputa = 4, b = 6

Output12

Inputa = 15, b = 20

Output60

Inputa = 7, b = 1

Output7

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (gcd) because the LCM and gcd are related. The LCM is the smallest number divisible by both numbers. Using the formula lcm = (a / gcd) * b helps avoid large intermediate multiplication and ensures correct calculation.

Algorithm

1

Get input values for two numbers a and b

2

Calculate gcd of a and b using the Euclidean algorithm

3

Calculate lcm using the formula lcm = (a / gcd) * b

4

Return or print the lcm value

Code

cpp

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    int lcm = (a / gcd(a, b)) * b;
    cout << "LCM of " << a << " and " << b << " is " << lcm << endl;
    return 0;
}

Output

Enter two numbers: 15 20
LCM of 15 and 20 is 60

Dry Run

Let's trace the input a=15 and b=20 through the code

1

Calculate gcd(15, 20)

20 != 0, temp=20, b=15%20=15, a=20 Next: 15 != 0, temp=15, b=20%15=5, a=15 Next: 5 != 0, temp=5, b=15%5=0, a=5 Loop ends, gcd=5

2

Calculate lcm

lcm = (15 / 5) * 20 = 3 * 20 = 60

a	b	temp	b after modulo
15	20	20	15
20	15	15	5
15	5	5	0

Why This Works

Step 1: Why use gcd?

The gcd helps find the largest number dividing both inputs, which is key to calculating the LCM efficiently.

Step 2: Formula for LCM

LCM is calculated as (a / gcd) * b to avoid overflow and get the smallest common multiple.

Step 3: Euclidean algorithm

The gcd is found using the Euclidean algorithm by repeatedly replacing the larger number with the remainder until zero.

Alternative Approaches

Using std::lcm from C++17

cpp

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    cout << "LCM of " << a << " and " << b << " is " << lcm(a, b) << endl;
    return 0;
}

This uses the built-in <code>std::lcm</code> function available from C++17, which is simpler and less error-prone.

Brute force approach

cpp

#include <iostream>
using namespace std;

int main() {
    int a, b, max_val, lcm;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    max_val = (a > b) ? a : b;
    lcm = max_val;
    while (true) {
        if (lcm % a == 0 && lcm % b == 0) {
            break;
        }
        lcm++;
    }
    cout << "LCM of " << a << " and " << b << " is " << lcm << endl;
    return 0;
}

This brute force method checks multiples starting from the max of a and b until it finds the LCM; it is simple but inefficient for large numbers.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm for gcd runs in O(log(min(a, b))) time, which dominates the calculation. The LCM calculation is then O(1).

Space Complexity

The program uses a constant amount of extra space, only storing a few integers.

Which Approach is Fastest?

Using the Euclidean algorithm with the formula is fastest and most efficient. The brute force method is slow for large inputs, and std::lcm is the simplest and recommended if C++17 is available.

Approach	Time	Space	Best For
Euclidean gcd + formula	O(log(min(a,b)))	O(1)	All input sizes, efficient
std::lcm (C++17)	O(log(min(a,b)))	O(1)	Simple code, modern C++
Brute force	O(a*b) worst	O(1)	Small inputs, learning purpose