Find LCM of Two Numbers in Java: Using GCD (Efficient Method)

Introduction

Finding the Least Common Multiple (LCM) is a natural follow-up to learning the Greatest Common Divisor (GCD) because the most efficient way to calculate the LCM doesn't require a completely new algorithm. Instead, it builds directly on the Euclidean algorithm you've already learned for finding the GCD.

Although it's possible to find the LCM by checking multiples one by one, the standard approach in mathematics and programming is to use the elegant relationship between LCM and GCD, allowing the result to be computed in logarithmic time.

In this guide, you'll learn the brute-force method, the efficient GCD-based formula, how to calculate the LCM of multiple numbers, and the mathematical reason why the famous LCM-GCD relationship works.

What Is LCM (Least Common Multiple)?

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that both numbers divide exactly without leaving a remainder.

For example:

Multiples of 4:
4, 8, 12, 16, 20, ...

Multiples of 6:
6, 12, 18, 24, ...

The first common multiple is:

12

Therefore,

LCM(4,6) = 12

Real-World Applications

LCM is used in:

• Finding common denominators for fractions

• Scheduling repeating events

• Synchronizing cycles

• Manufacturing and production schedules

• Clock and timing problems

Method 1: Brute Force Approach

The simplest approach repeatedly checks multiples of the larger number until it finds one divisible by both numbers.

Java Program

public class LCMBruteForce {

    public static void main(String[] args) {

        int a = 4;
        int b = 6;

        int max = Math.max(a, b);
        int lcm = max;

        while (true) {

            if (lcm % a == 0 && lcm % b == 0) {
                break;
            }

            lcm += max;
        }

        System.out.println("LCM of " + a + " and " + b + " is: " + lcm);
    }
}

Output

LCM of 4 and 6 is: 12

Step-by-Step Trace

The first common multiple found is 12, so it is the LCM.

Drawback

For numbers with very large LCM values, the loop may perform many iterations before finding the answer.

Method 2: Using the GCD Formula (Efficient)

The standard solution uses the mathematical identity:

LCM(a,b)

=

(a × b) / GCD(a,b)

Java Program

public class LCMUsingGCD {

    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;
        int b = 6;

        int lcm = (a * b) / gcd(a, b);

        System.out.println("LCM of " + a + " and " + b + " is: " + lcm);
    }
}

Output

LCM of 4 and 6 is: 12

How It Works

First calculate:

GCD(4,6)

=

2

Then:

LCM

=

(4 × 6) / 2

=

24 / 2

=

12

The GCD calculation dominates the running time, giving an overall complexity of:

O(log(min(a,b)))

Avoiding Integer Overflow

For large numbers, this expression:

(a * b) / gcd(a, b)

may overflow before the division happens.

A safer implementation divides first:

int lcm = (a / gcd(a, b)) * b;

This reduces the intermediate value before multiplication and significantly lowers the chance of overflow.

Method 3: Finding LCM of an Array

LCM is associative, meaning:

LCM(a,b,c)

=

LCM(LCM(a,b),c)

This makes it easy to compute the LCM of multiple numbers.

Java Program

public class LCMOfArray {

    static int gcd(int a, int b) {

        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return (a / gcd(a, b)) * b;
    }

    public static void main(String[] args) {

        int[] numbers = {4, 6, 8};

        int result = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            result = lcm(result, numbers[i]);
        }

        System.out.println("LCM of the array is: " + result);
    }
}

Output

LCM of the array is: 24

How It Works

The running LCM evolves like this:

LCM(4,6)

↓

12

↓

LCM(12,8)

↓

24

The final result is the smallest number divisible by every element in the array.

Why the LCM Formula Works

The mathematical identity

LCM(a,b)

=

(a × b) / GCD(a,b)

comes from prime factorization.

Suppose:

12 = 2² × 3

18 = 2 × 3²

Their GCD contains only the common prime factors:

2 × 3 = 6

Multiplying the two numbers gives:

12 × 18 = 216

Notice that the common factors have been counted twice.

Dividing by the GCD removes the extra copy:

216 / 6 = 36

which is exactly the LCM.

How Java Handles This Internally

Brute Force

Variables such as:

• a

• b

• max

• lcm

are primitive integers stored on the stack.

The loop repeatedly updates the candidate LCM.

GCD Formula

The recursive gcd() function briefly uses the call stack.

Once the GCD is returned, only a single multiplication and division are performed.

Array Version

The array:

int[] numbers

is allocated on the heap.

The running LCM is stored as a primitive integer on the stack.

Real-Life Analogy

Imagine two buses.

• Bus A arrives every 4 minutes.

• Bus B arrives every 6 minutes.

If both buses leave together now, when will they arrive together again?

The answer is:

LCM(4,6)

=

12 minutes

Bus A arrives at:

4, 8, 12

Bus B arrives at:

6, 12

Both meet again after 12 minutes.

This is exactly the type of scheduling problem solved using LCM.

Comparison Table

Best Practices

• Always use the GCD-based formula instead of brute force.

• Divide before multiplying to reduce overflow risk.

• Reuse a tested gcd() implementation.

• Use long instead of int if large values are expected.

• Compute array LCM using repeated pairwise calculations.

Common Mistakes

Multiplying Before Dividing

This can overflow:

(a * b) / gcd

Instead use:

(a / gcd) * b

Using Brute Force for Large Numbers

Checking every multiple becomes increasingly slow.

The GCD formula is dramatically faster.

Forgetting That LCM Depends on GCD

The efficient algorithm requires first calculating the GCD.

Confusing GCD and LCM

Remember:

• GCD → Largest common divisor

• LCM → Smallest common multiple

Incorrect Array Initialization

Always initialize:

int result = numbers[0];

before processing the remaining elements.

Expert Tips

A strong interview answer is:

"The most efficient way to calculate the LCM is by first computing the GCD using the Euclidean algorithm, then applying the formula LCM(a, b) = (a / GCD(a, b)) × b. Dividing before multiplying helps avoid integer overflow while preserving the same mathematical result."

Mentioning the overflow-safe version of the formula is a detail that demonstrates production-level programming awareness.

Pros and Cons

Frequently Asked Questions

What is the fastest way to find the LCM?

Use:

LCM(a,b)

=

(a × b) / GCD(a,b)

with the Euclidean algorithm for the GCD.

What is the relationship between LCM and GCD?

Multiplying two numbers counts their shared factors twice.

Dividing by the GCD removes the duplicate factors, leaving the LCM.

How can I avoid integer overflow?

Use:

(a / gcd(a,b)) * b

instead of multiplying first.

Can I find the LCM of multiple numbers?

Yes.

Repeatedly apply the two-number LCM calculation across the array.

What is the time complexity?

Using the GCD formula:

O(log(min(a,b)))

Is there a brute-force approach?

Yes.

Keep checking multiples until one is divisible by both numbers.

However, it is much slower than the GCD-based solution.

Where is LCM used?

Common applications include:

• Fraction addition

• Scheduling

• Synchronizing repeating events

• Clock problems

• Manufacturing processes

What is the LCM of two coprime numbers?

If:

GCD(a,b) = 1

then:

LCM = a × b

Can LCM be calculated for negative numbers?

LCM is generally defined for positive integers.

If negative numbers are supplied, take their absolute values before calculating.

Is LCM a common interview question?

Yes.

It is frequently paired with GCD questions to test whether candidates know the mathematical relationship between the two.

Which data type should I use?

Use:

• int for small numbers

• long for larger values

• BigInteger when values exceed the range of primitive types

Why should I learn GCD before LCM?

Because the most efficient LCM algorithm directly depends on the Euclidean algorithm for calculating the GCD.