#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

LCM of Two Numbers in C++

This program finds the Least Common Multiple (LCM) of two numbers. LCM is the smallest positive integer that is divisible by both numbers. The program uses an efficient method: first finding the GCD (Greatest Common Divisor), then calculating LCM using the mathematical relationship between GCD and LCM.

What is LCM (Least Common Multiple)?

LCM of two numbers is the smallest number that is a multiple of both numbers.

Examples:

• LCM of 12 and 18:
  • Multiples of 12: 12, 24, 36, 48, 60, 72, ...
  • Multiples of 18: 18, 36, 54, 72, 90, ...
  • Common multiples: 36, 72, 108, ...

  • LCM = 36 (smallest common multiple)

LCM is used in:

• Adding/subtracting fractions with different denominators
• Finding when events repeat (e.g., two clocks chiming together)
• Scheduling problems
• Many mathematical applications

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:

• GCD contains the common factors of both numbers
• When we multiply a and b, we get all factors (common and unique)
• Dividing by GCD removes the common factors, leaving only what's needed for LCM

Example with 12 and 18:

• GCD(12, 18) = 6
• LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = ## 36 ✅

Why This Method is Efficient

Naive approach (checking multiples):

• Time complexity: O(max(a, b))

Our approach (using GCD):

• Find GCD: O(log(min(a, b)))
• Calculate LCM: O(1) (just multiplication and division)

• Total: O(log(min(a, b)))

• Much faster!

Summary

• LCM is the smallest number divisible by both given numbers
• Efficient method: LCM(a, b) = (a × b) / GCD(a, b)
• First find GCD using Euclidean algorithm
• Then calculate LCM using the formula
• This method is much faster than checking multiples
• Understanding GCD and LCM relationship is crucial for many mathematical problems

This program demonstrates:

• How to combine algorithms (GCD + LCM calculation)
• Using mathematical relationships for efficiency
• The importance of saving original values
• Practical application of number theory

Mastering LCM calculation helps in:

• Fraction arithmetic
• Solving scheduling problems
• Finding common denominators
• Many real-world applications