Find LCM in Java

What you’ll learn

  • How to compute LCM using gcd formula.
  • How to implement Euclidean gcd in Java.
  • A brute-scan approach for concept clarity.

Prerequisites

  • Basic Java syntax, loops, conditionals, and methods.
  • Comfort with integer arithmetic and console input/output.

Math definition

This problem is driven by a deterministic numeric rule: for each valid input, apply the same formula repeatedly and classify the result.

Intuition with examples

Work a small input by hand first, then map each step to one Java loop iteration. This makes the control flow and stopping condition clear.

Live preview

Live result
Press "Compute lcm".

Algorithm

Goal: compute lcm(a,b) safely for integer inputs.

Find gcd with Euclid

Iterate (a, b) = (b, a % b) until b == 0; the remaining a is gcd.

Compute lcm from gcd

If either input is zero return 0; else use (a / gcd) * b in a wider type.

📜 Pseudocode

Pseudocode
function gcd(a, b):
    while b != 0:
        (a, b) = (b, a mod b)
    return a

function lcm(a, b):
    if a == 0 or b == 0:
        return 0
    g = gcd(a, b)
    return (a / g) * b
1

LCM from gcd (12, 18)

java
public class Main {
    static int findGcd(int num1, int num2) {
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        while (num2 != 0) {
            int temp = num2;
            num2 = num1 % num2;
            num1 = temp;
        }
        return num1;
    }

    static long findLcmLong(int num1, int num2) {
        if (num1 == 0 || num2 == 0) return 0L;
        int g = findGcd(num1, num2);
        return (long) (num1 / g) * (long) num2;
    }

    public static void main(String[] args) {
        int number1 = 12;
        int number2 = 18;
        long lcm = findLcmLong(number1, number2);
        System.out.println("LCM of " + number1 + " and " + number2 + " is: " + lcm);
    }
}
📤 Output
LCM of 12 and 18 is: 36
2

Brute scan approach

java
public class Main {
    static int lcmScanPositive(int a, int b) {
        if (a <= 0 || b <= 0) return 0;
        int step = Math.max(a, b);
        int m = step;
        while (m % a != 0 || m % b != 0) {
            m += step;
        }
        return m;
    }

    public static void main(String[] args) {
        int number1 = 12;
        int number2 = 18;
        System.out.println("LCM of " + number1 + " and " + number2 + " is: " + lcmScanPositive(number1, number2));
    }
}
📤 Output
LCM of 12 and 18 is: 36

Optimization notes

Keep it simple. Prefer clear loops and method extraction before micro-optimizations.

Reuse computed values. Avoid recomputing the same sub-result inside nested loops.

❓ FAQ

LCM is the smallest positive number divisible by both given positive integers.
For nonnegative integers, gcd(a,b) * lcm(a,b) = a*b, so lcm = (a/gcd) * b.
Conventionally lcm(0,n) is 0.
It reduces overflow risk compared to computing a*b first.
This page uses nonnegative inputs and returns nonnegative lcm.
GCD-based method is O(log min(a,b)); brute scan is slower.

🔄 Input / output examples

Use the sample programs as reference: provide valid numeric input and verify the output pattern matches the problem definition.

(a, b)gcdlcm
(12, 18)636
(4, 6)212
(17, 13)1221
(0, 9)90

Edge cases

Bounds

Smallest valid input

Confirm behavior for minimum accepted values.

Validation

Invalid input

Guard against non-numeric or out-of-range values when input is user-provided.

⏱️ Time and space complexity

MethodTimeExtra space
gcd + formulaO(log min(a,b))O(1)
Brute scanO(lcm / max(a,b)) in worst caseO(1)

Summary

  • Use a direct Java implementation of the numeric rule.
  • Validate input and test boundary cases.
  • Discuss complexity clearly in interviews.
Did you know?

For nonnegative integers a and b, gcd(a,b) * lcm(a,b) = a * b. This identity helps compute lcm quickly once gcd is known.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

8 people found this page helpful

Java Program to Check Harshad Number Java Program to Check Leap Year