Find LCM (Using GCD) in Java
Problem
The least common multiple (LCM) of two numbers is the smallest number that both of them divide into evenly.
Given two integers, find their least common multiple.
Java Program
public class FindLCM {
public static void main(String[] args) {
int a = 4, b = 6;
int larger = Math.max(a, b);
int lcm = larger;
while (true) {
if (lcm % a == 0 && lcm % b == 0) break; // found a multiple divisible by both
lcm += larger; // try the next multiple of the larger number
}
System.out.println("LCM: " + lcm);
}
}Output
Core Logic
Trying successive multiples of the larger number, and stopping at the first one that's also divisible by the smaller number, finds the least common multiple directly.
- 1
largerholds whichever of the two numbers is bigger, since the LCM is always a multiple of it. - 2
lcmstarts atlargeritself, the smallest candidate multiple worth trying. - 3Each iteration checks whether the current
lcmis divisible by bothaandb. - 4If not,
lcmis increased bylargeragain, moving to the next multiple, until a match is found.
4 and 6, larger is 6; trying 6 fails (not divisible by 4), but the next multiple, 12, is divisible by both.Key Point: Only multiples of the larger number ever need to be tried — the LCM can never be smaller than the larger of the two input numbers.
Why: In the worst case (when a and b are coprime) the loop tries min(a, b) multiples before finding one divisible by both, using only a couple of variables regardless of the numbers' size.
Key Concepts
Approach 2: Using GCD
public class FindLCMUsingGCD {
static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
public static void main(String[] args) {
int a = 4, b = 6;
// lcm(a, b) * gcd(a, b) = a * b, solved for the lcm
int lcm = (a * b) / gcd(a, b);
System.out.println("LCM: " + lcm);
}
}
Output
Core Logic
The LCM and GCD of two numbers are always related by a fixed formula — once the GCD is known, the LCM falls out of a single multiplication and division.
- 1
gcd(a, b)computes the greatest common divisor using the Euclidean algorithm. - 2
(a * b) / gcd(a, b)applies the identitylcm(a, b) × gcd(a, b) = a × b, solved for the LCM. - 3No multiples are tried directly — the answer comes straight out of the formula.
4 and 6, gcd(4, 6) = 2, so lcm(4, 6) = (4 × 6) / 2 = 12.Key Point: This reaches the answer almost instantly regardless of how large the numbers are, since it only needs the fast Euclidean algorithm plus one multiplication and division.
Why: Computing gcd() dominates the cost, since the multiplication and division that follow are both constant-time — the recursion depth of gcd() is what the space cost reflects.