Medium · number theory

Least Common Multiple

You already have gcd from Greatest Common Divisor. LCM is just a / gcd(a,b) * b — but the order matters, or the product overflows.

At a glanceLCM is a / gcd(a, b) * b — divide before multiplying: at 10⁴ the product would still fit, but that habit is what keeps it correct when the inputs grow.

Problem

Input: two lines, each with one integer: a then b (1 ≤ a, b ≤ 10000).

Output: their least common multiple.

Samples:

InputOutput
4
6		12
3
5		15
12
18		36

Your solution

main.cpp — your solution
Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — the formula

lcm(a,b) = a * b / gcd(a,b). But write it as a / gcd(a,b) * b — dividing first keeps the intermediate value small, so it won't overflow a 32-bit int for the ranges here.

Hint 2 — equal numbers

If a == b, the answer is just a — and the formula gives that too, no special case needed. Watch the order of operations: a / gcd * b is integer math, so do the division before the multiplication.

Solution (try it first!) 
#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a / gcd(a, b) * b << endl;
    return 0;
}

Now you can scale: how many multiples of k fit between two bounds, or reduce a fraction with gcd then find a common denominator with lcm. Next: Armstrong Number.

Deep dive

Why this works

The identity a * b = gcd(a,b) * lcm(a,b) is the whole trick — once you have gcd, lcm is one division away. No loop over multiples, no guessing.

The cost

O(log min(a,b)) time, the same as Euclid's gcd. O(1) space. The a / gcd * b order keeps the intermediate inside 32 bits for these inputs.

Where it goes wrong

  • Writing a * b / gcd(a,b) multiplies first; for large a and b that intermediate overflows int and the answer comes out negative.
  • Forgetting that gcd must return the divisor itself — swapping a = b; b = a % b without saving the remainder first can loop forever or return 0.

Next step

Same function, new use: reduce a fraction to lowest terms by dividing both parts by gcd. Armstrong Number flips the digits-and-powers idea around.

Two things to remember

  • lcm(a,b) = a / gcd(a,b) * b — divide before you multiply.
  • Euclid's gcd is the reusable tool; most number-theory problems are one call away from it.
🐞 This version fails — open it and try

Prints the product instead of the LCM — 4 6 gives 24, the judge wants 12

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a * b << endl;   // product, not lcm
    return 0;
}