LCM of Two Numbers
Program to find Least Common Multiple of two numbers
C++ LCM of Two Numbers Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
using namespace std;
int main() {
int a, b, gcd, lcm;
cout << "Enter two numbers: ";
cin >> a >> b;
int originalA = a, originalB = b;
// Find GCD first
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
gcd = a;
// LCM = (a * b) / GCD
lcm = (originalA * originalB) / gcd;
cout << "LCM of " << originalA << " and " << originalB << " is: " << lcm << endl;
return 0;
}Enter two numbers: 12 18 LCM of 12 and 18 is: 36
Understanding LCM of Two Numbers
---
1. What is LCM (Least Common Multiple)?
LCM of two numbers is the smallest number that is a multiple of both numbers.
Examples:
-
LCM = 36
(smallest common multiple)
-
LCM = 12
LCM is used in:
---
2. The Relationship Between GCD and LCM
There's a beautiful mathematical relationship:
LCM(a, b) × GCD(a, b) = a × b
Rearranging:
LCM(a, b) = (a × b) / GCD(a, b)
Why this works:
Example with 12 and 18:
36
✅
---
3. Header File: #include <iostream>
#include <iostream>
Provides:
cout → for displaying outputcin → for reading input---
4. Declaring Variables
int a, b, gcd, lcm;
Variable `a` and `b`:
Variable `gcd`:
Variable `lcm`:
Saving original values:
int originalA = a, originalB = b;
a and b will be modified---
5. Taking Input From User
cin >> a >> b;
a and bExample:
12 18
a = 12, b = 18---
6. Finding GCD Using Euclidean Algorithm
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
gcd = a;
This is the Euclidean algorithm we learned in the GCD program.
// Find GCD firstStep-by-step (for a = 12, b = 18):
Iteration 1:
temp = 18b = 12 % 18 = 12a = 18a = 18, b = 12Iteration 2:
temp = 12b = 18 % 12 = 6a = 12a = 12, b = 6Iteration 3:
temp = 6b = 12 % 6 = 0a = 6a = 6, b = 0Result:
gcd = 6
---
7. Calculating LCM Using the Formula
lcm = (originalA * originalB) / gcd;
Why use originalA and originalB?
a and b were modified during GCD calculationa now contains the GCD (6)b is now 0Calculation:
lcm = (12 × 18) / 6lcm = 216 / 6lcm = 36 ✅---
8. Why This Method is Efficient
Naive approach (checking multiples):
-
Time complexity: O(max(a, b))
Our approach (using GCD):
-
Total: O(log(min(a, b)))
Example:
---
9. Complete Example Walkthrough
Input:
a = 12, b = 18
Step 1: Save originals
originalA = 12, originalB = 18Step 2: Find GCD
gcd = 6Step 3: Calculate LCM
lcm = (12 × 18) / 6lcm = 216 / 6lcm = 36Step 4: Display result
---
10. Verification
Let's verify the result:
-
Multiples of 12:
12, 24, 36, 48, 60, ...
-
Multiples of 18:
18, 36, 54, 72, ...
-
Common multiples:
36, 72, 108, ...
-
Smallest common multiple:
36 ✅
Also verify the relationship:
-
6 × 36 = 216
-
12 × 18 = 216
✅
---
11. Edge Cases
Case 1: One number is a multiple of the other
Case 2: Both numbers are equal
Case 3: Coprime numbers (GCD = 1)
---
12. Displaying the Result
This prints:
Output:
LCM of 12 and 18 is: 36
---
Summary
This program demonstrates:
Mastering LCM calculation helps in:
The relationship between GCD and LCM is one of the most elegant in mathematics, and this program shows how to use it efficiently in programming.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for LCM of Two Numbers
This C++ program is part of the "Loop Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.