Java Program to Find LCM of Two Numbers

To find the LCM of two numbers in Java, use the formula lcm = (a * b) / gcd(a, b) where gcd is the greatest common divisor calculated using a method like Euclid's algorithm.

Examples

Inputa = 4, b = 6

OutputLCM is 12

Inputa = 21, b = 6

OutputLCM is 42

Inputa = 0, b = 5

OutputLCM is 0

How to Think About It

To find the LCM of two numbers, first find their greatest common divisor (GCD) because the LCM is related to the GCD by the formula: multiply the two numbers and divide by their GCD. This avoids checking multiples one by one and is efficient.

Algorithm

1

Get input numbers a and b

2

Find the GCD of a and b using Euclid's algorithm

3

Calculate LCM as (a * b) / GCD

4

Return or print the LCM

Code

java

public class LCM {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        return (a / gcd(a, b)) * b;
    }

    public static void main(String[] args) {
        int a = 4, b = 6;
        System.out.println("LCM is " + lcm(a, b));
    }
}

Output

LCM is 12

Dry Run

Let's trace the input a=4 and b=6 through the code

1

Calculate GCD

Start with a=4, b=6. Compute a % b = 4 % 6 = 4. Swap: a=6, b=4.

2

Continue GCD calculation

Now a=6, b=4. Compute a % b = 6 % 4 = 2. Swap: a=4, b=2.

3

Continue GCD calculation

Now a=4, b=2. Compute a % b = 4 % 2 = 0. Swap: a=2, b=0.

4

GCD found

Since b=0, GCD is a=2.

5

Calculate LCM

LCM = (4 / 2) * 6 = 2 * 6 = 12.

a	b	a % b	New a	New b
4	6	4	6	4
6	4	2	4	2
4	2	0	2	0

Why This Works

Step 1: Why find GCD first?

The LCM is related to the GCD by the formula lcm = (a * b) / gcd, so finding the GCD simplifies the calculation.

Step 2: How Euclid's algorithm works

Euclid's algorithm finds the GCD by repeatedly replacing the larger number with the remainder until the remainder is zero.

Step 3: Calculating LCM using GCD

After finding the GCD, dividing one number by the GCD and multiplying by the other number gives the LCM without overflow risk.

Alternative Approaches

Brute Force

java

public class LCMBruteForce {
    public static int lcm(int a, int b) {
        int max = Math.max(a, b);
        int lcm = max;
        while (true) {
            if (lcm % a == 0 && lcm % b == 0) {
                return lcm;
            }
            lcm++;
        }
    }

    public static void main(String[] args) {
        System.out.println("LCM is " + lcm(4, 6));
    }
}

Simple but inefficient for large numbers because it checks multiples one by one.

Using Java 8 Math API

java

import java.util.*;
public class LCMJava8 {
    public static void main(String[] args) {
        int a = 4, b = 6;
        int gcd = Math.gcd(a, b); // Note: Java 8 does not have gcd, Java 9+ has gcd in Math
        int lcm = (a / gcd) * b;
        System.out.println("LCM is " + lcm);
    }
}

Requires Java 9 or higher for Math.gcd; simpler but less compatible with older versions.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

Finding GCD using Euclid's algorithm takes O(log(min(a,b))) time because the remainder reduces quickly each step.

Space Complexity

The algorithm uses constant extra space O(1) as it only stores a few variables.

Which Approach is Fastest?

Using GCD is much faster than brute force, especially for large numbers, because brute force can take very long checking multiples.

Approach	Time	Space	Best For
GCD-based	O(log(min(a,b)))	O(1)	All input sizes, efficient
Brute Force	O(a*b)	O(1)	Very small numbers only
Java 9+ Math.gcd	O(log(min(a,b)))	O(1)	Modern Java versions, concise code