LCM of Two Numbers in Java

LCM is widely used in scheduling algorithms to sync tasks efficiently, cryptography for secure data transmission, and even in game development to manage frame rates. Whether you're working on a financial app, a networking system, or just solving coding problems, knowing how to find LCM in Java can come in handy. 

In this tutorial, you'll learn how to find the LCM of two numbers in Java using different methods and understand its real-world applications.

Improve your Java programming skills with our Software Development courses — take the next step in your learning journey! 

Understanding LCM

LCM (Least Common Multiple) is the smallest number that two or more numbers can divide evenly. It’s a fundamental concept in math, but it’s also super useful in programming.

LCM and GCD (Greatest Common Divisor) are mathematically linked by the equation LCM(a, b) × GCD(a, b) = a × b. The product of two numbers is always equal to the product of their LCM and GCD:

LCM(a,b)×GCD(a,b)=a×b

This formula allows you to compute LCM efficiently using GCD, which is faster than brute-force methods. However, directly multiplying a × b can lead to integer overflow, especially for large numbers. A safer approach is:

LCM (a,b)=aGCD(a,b)b

By computing GCD first, we reduce the risk of overflow and ensure an efficient LCM calculation. This method is significantly faster than brute-force approaches.

Now that you understand what LCM is and its relationship with GCD, let's explore different ways to compute LCM of two numbers in Java. 

Methods to Find LCM in Java

LCM of two numbers in Java can be calculated in different ways, each suited for specific cases. The brute force method is simple but slow, best for small inputs. The GCD-based approach is the most efficient, ideal for performance-critical applications. 

The recursive method is concise but may be inefficient for very large numbers. The best method depends on the input size and performance requirements. Let’s explore each in detail.

Here, you'll explore three main approaches:

1. Using Loops (Brute Force Method)

In this approach, you start with the maximum of the two numbers and keep incrementing it until you find a number that is divisible by both. This method is simple but inefficient for large numbers.

Java Program for LCM (Brute Force Method):

import java.util.Scanner;

public class LCMBruteForce {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input two numbers
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        scanner.close();
        
        // Find maximum of the two numbers
        int max = Math.max(num1, num2);
        
        // Brute force approach: Keep increasing max until it is divisible by both numbers
        while (true) {
            if (max % num1 == 0 && max % num2 == 0) {
                System.out.println("LCM of " + num1 + " and " + num2 + " is: " + max);
                break;
            }
            max++; // Increment the number to check for divisibility
        }
    }
}

Explanation:

Step 1: Take user input for two numbers.

Step 2: Find the maximum of the two numbers since LCM is at least as large as the biggest number.

Step 3: Use a loop to check if max is divisible by both numbers. If not, increment and check again.

Step 4: Once found, print the LCM and exit the loop

Output Example:

Enter first number: 6
Enter second number: 8
LCM of 6 and 8 is: 24

Time Complexity:

• Worst case: O(ab), where a and b are input numbers.
• Efficiency: Poor for large numbers.

Also Read: For-Each Loop in Java [With Coding Examples]

2. Using GCD (Euclidean Algorithm)

A more efficient way to compute LCM is by using the formula:

LCM (a,b)=(ab)GCD (a,b)

The GCD (Greatest Common Divisor) is calculated using the Euclidean algorithm, which finds the GCD efficiently using recursion or iteration.

Java Program for LCM (Using GCD):

import java.util.Scanner;

public class LCMUsingGCD {
    // Function to compute GCD using the Euclidean algorithm
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // Function to compute LCM using GCD
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b); // Using LCM formula
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input two numbers
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        scanner.close();
        
        // Compute and print LCM
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
    }
}

Explanation:

Step 1: Define a function to calculate GCD using the Euclidean algorithm:

• Keep taking the remainder (a % b) until b becomes 0.
• The last non-zero value of a is the GCD.

Step 2: Use the LCM formula LCM(a, b) = (a × b) / GCD(a, b).

Step 3: Print the LCM result.

Output Example:

Enter first number: 6
Enter second number: 8
LCM of 6 and 8 is: 24

Time Complexity:

• GCD Computation: O(log(min(a,b))), using the Euclidean algorithm.
• LCM Calculation: O(log(min(a,b))), as it depends on GCD and involves multiplication and division.
• Overall Efficiency: Much better than brute force, especially for large numbers, due to logarithmic complexity.

Also Read: Math for Data Science: Linear Algebra, Statistics, and More

3. Using Recursion

This method recursively finds the GCD, then uses it to compute LCM. Recursion simplifies the code but may lead to stack overflow for extremely large inputs.

Java Program for LCM (Using Recursion):

import java.util.Scanner;

public class LCMRecursive {
    // Recursive function to find GCD
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    // Function to compute LCM using GCD
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b); // Using LCM formula
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input two numbers
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        scanner.close();
        
        // Compute and print LCM
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
    }
}

Explanation:

Step 1: Define a recursive function for GCD:

• If b == 0, return a (base case).
• Otherwise, call gcd(b, a % b) recursively.

Step 2: Use the LCM formula as before.

Step 3: Print the LCM result.

Output Example:

Enter first number: 6
Enter second number: 8
LCM of 6 and 8 is: 24

Time Complexity:

• Recursive GCD: O(log(min(a,b)))
• LCM Calculation: O(1)
• Overall Efficiency: Similar to the iterative GCD method but uses recursion.

Here’s a comparison of methods:

The GCD-based method is best for real-world applications due to its efficiency. 

Also Read: Recursion in Data Structures: Types, Algorithms, and Applications

While these methods work well in most cases, certain edge cases can cause incorrect results or performance issues. Special cases like zero inputs, negative numbers, and large values need careful handling. 

Handling Edge Cases in LCM Calculation

When working with a Java program for LCM, it's essential to handle special cases correctly to avoid errors or unexpected behavior. Let's go through some key edge cases:

1. LCM of Zero and a Number

Issue: Mathematically, LCM is undefined if one of the numbers is zero because any number multiplied by zero is zero. In programming, division by zero leads to an error.

Solution: If either number is zero, the LCM should be defined as zero because multiplying any number by zero results in zero.

Code Fix: By convention, LCM(0, x) is treated as 0 since any number multiplied by zero is zero.

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

Example Output:

LCM of 0 and 5 is: 0
LCM of 0 and 0 is: 0

2. LCM of Negative Numbers

Issue: The mathematical definition of LCM considers only positive integers. If negative numbers are used, the standard formula may still work, but it can produce a negative LCM.

Solution: Use the absolute value of numbers to ensure LCM is always positive. The formula remains the same: LCM(a, b) = (a × b) / GCD(a, b).

Code Fix: Modify the lcm function to handle negative numbers properly:

public static int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0; // LCM of zero is zero
    return Math.abs(a * b) / gcd(Math.abs(a), Math.abs(b)); // Ensure LCM is positive
}

Example Output:

LCM of -6 and 8 is: 24
LCM of -12 and -15 is: 60

3. Handling Large Numbers in Java

Issue: Java’s int type has a limit of 2,147,483,647 (2^31 - 1), and multiplying two large numbers can cause an overflow. For example, LCM(1_000_000, 2_000_000) exceeds the int range.

Solution: Use long instead of int to handle larger values. If even long is not enough, use BigInteger from java.math for unlimited precision.

Code Fix (Using long):

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

public static long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0; // LCM of zero is zero
    return Math.abs(a / gcd(a, b) * b); // Prevent overflow
}

public static void main(String[] args) {
    long num1 = 1000000, num2 = 2000000;
    System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
}

Example Output:

LCM of 1000000 and 2000000 is: 2000000

Using BigInteger (For Extremely Large Numbers):

import java.math.BigInteger;

public class LCMBigInteger {
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
    }

    public static BigInteger lcm(BigInteger a, BigInteger b) {
        if (a.equals(BigInteger.ZERO) || b.equals(BigInteger.ZERO)) return BigInteger.ZERO;
        return a.multiply(b).divide(gcd(a, b)); // Use BigInteger methods
    }

    public static void main(String[] args) {
        BigInteger num1 = new BigInteger("1000000000000");
        BigInteger num2 = new BigInteger("2000000000000");

        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm(num1, num2));
    }
}

Example Output:

LCM of 1000000000000 and 2000000000000 is: 2000000000000

Handling these cases ensures that our LCM function is robust, efficient, and reliable across different input values. 

Also Read: Exploring the 14 Key Advantages of Java: Why It Remains a Developer's Top Choice in 2025

Handling edge cases ensures accurate LCM computation. Now, let’s explore the real-world applications of LCM in Java.

Practical Applications of LCM in Java

LCM (Least Common Multiple) is not just a mathematical concept; it has real-world applications in cryptography, computer science, networking, and scheduling. Here are some key areas where LCM is used in Java programming:

1. Cryptography (RSA Algorithm)

Use Case: LCM plays a crucial role in key generation for the RSA encryption algorithm, one of the most widely used encryption methods.

How it Works: In RSA, the LCM of two prime numbers is used to calculate the Euler’s totient function (φ), which helps in generating the encryption and decryption keys.

Java Code:

import java.math.BigInteger;

public class RSAKeyGeneration {
    public static BigInteger gcd(BigInteger a, BigInteger b) {
        return b.equals(BigInteger.ZERO) ? a : gcd(b, a.mod(b));
    }

    public static BigInteger lcm(BigInteger a, BigInteger b) {
        return a.multiply(b).divide(gcd(a, b)); // Using LCM formula
    }

    public static void main(String[] args) {
        BigInteger p = new BigInteger("61"); // Prime number
        BigInteger q = new BigInteger("53"); // Prime number
        BigInteger lcmValue = lcm(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));

        System.out.println("LCM for RSA Key Generation: " + lcmValue);
    }
}

Example Output:

LCM for RSA Key Generation: 780

Why It’s Important: RSA encryption relies on LCM to calculate key values efficiently.

Also Read: Cryptography in Blockchain: Key Types and Algorithms Explained

2. Computer Science (Data Synchronization & Buffering)

Use Case: LCM is used in data buffering, memory management, and caching where different buffer sizes need to be synchronized.

Example: If a video player needs to sync an audio buffer (44ms) and a video buffer (60ms), LCM helps find the optimal synchronization time.

Also Read: Ultimate Guide to Synchronization in Java

3. Networking (Data Transmission & Scheduling)

Use Case: In network communication protocols, LCM helps in scheduling message packets over different frequencies.

Example: If two devices send packets every 5ms and 7ms, LCM helps determine when both packets align.

Java Code: Packet Synchronization

public class NetworkPacketSync {
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

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

    public static void main(String[] args) {
        int device1Rate = 5; // Packet every 5ms
        int device2Rate = 7; // Packet every 7ms

        int syncTime = lcm(device1Rate, device2Rate);
        System.out.println("Packets will synchronize every " + syncTime + " ms.");
    }
}

Example Output:

Packets will synchronize every 35 ms.

Why It’s Important: LCM ensures efficient data transmission without collisions.

4. Scheduling Tasks in a Multithreading Environment

Use Case: In multithreading, different tasks may have different execution intervals. LCM helps determine when tasks should execute together to optimize CPU usage.

Example: If a background task runs every 3 seconds and another every 4 seconds, LCM helps find when both will run simultaneously.

Java Code for Task Scheduling:

import java.util.Timer;
import java.util.TimerTask;

public class LCMTaskScheduler {
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

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

    public static void main(String[] args) {
        int task1Interval = 3; // Task 1 runs every 3 seconds
        int task2Interval = 4; // Task 2 runs every 4 seconds

        int syncTime = lcm(task1Interval, task2Interval); // Find LCM

        Timer timer = new Timer();
        
        timer.schedule(new TimerTask() {
            @Override
            public void run() {
                System.out.println("Task 1 executing...");
            }
        }, 0, task1Interval * 1000); // Run task1 every 3 seconds

        timer.schedule(new TimerTask() {
            @Override
            public void run() {
                System.out.println("Task 2 executing...");
            }
        }, 0, task2Interval * 1000); // Run task2 every 4 seconds

        System.out.println("Tasks will synchronize every " + syncTime + " seconds.");
    }
}

Example Output:

Tasks will synchronize every 12 seconds.
Task 1 executing...
Task 2 executing...
Task 1 executing...
Task 1 executing...
Task 2 executing...
(Both tasks execute together every 12 seconds)

Why It’s Important:

• Helps in task scheduling and CPU load balancing.
• Reduces unnecessary computations.

Also Read: Multithreading in Java - Learn with Examples

5. Robotics and Automation

Use Case: In robotics, different motors operate at different speeds. LCM helps find the best timing to synchronize movements.

Example: If one motor completes a cycle in 12ms and another in 15ms, LCM determines when they will align for smooth operation.

Also Read: 28 Robotics Project Ideas for Students in 2025

Test your understanding of LCM calculations in Java with this quiz. It’ll help reinforce the concepts discussed throughout the blog and ensure you're ready to apply them in your projects.

Quiz to Test Your Knowledge on LCM in Java

To solidify your understanding of LCM (Least Common Multiple) in Java, test your knowledge with this quiz. It will help reinforce the concepts discussed throughout the blog and ensure you're ready to apply them in your projects.

Assess your understanding of LCM calculations, methods, edge cases, and best practices. Answer the following multiple-choice questions:

1. Which of the following statements best defines LCM?

a) The largest number that divides two given numbers

b) The smallest number divisible by two given numbers

c) The sum of two numbers

d) The difference between two numbers

2. Which method is the most efficient for calculating LCM in Java?

a) Using a loop to check multiples

b) Using the formula LCM(a, b) = (a × b) / GCD(a, b)

c) Using recursion only

d) Generating all factors and finding the least common one

3. What is the time complexity of the brute force method for calculating LCM?

a) O(1)

b) O(log n)

c) O(a × b)

d) O(n²)

4. What is the relationship between LCM and GCD?

a) LCM × GCD = Product of the two numbers

b) LCM = GCD × (Sum of the numbers)

c) LCM and GCD are always equal

d) LCM is always smaller than GCD

5. Which of the following is an edge case when calculating LCM?

a) When both numbers are even

b) When one of the numbers is zero

c) When both numbers are prime

d) When one number is a multiple of the other

6. What is the LCM of 0 and any positive integer?

a) The integer itself

b) 0

c) 1

d) Undefined

7. Why should you use long or BigInteger when computing LCM?

a) To speed up computation

b) To handle negative numbers

c) To prevent integer overflow when multiplying large numbers

d) To make the code more complex

8. What will happen if you try to calculate LCM using (a * b) / gcd(a, b) without handling overflow?

a) The calculation will always be correct

b) The program may produce incorrect results due to integer overflow

c) It will always throw an ArithmeticException

d) Java will automatically switch to BigInteger

9. How can you efficiently compute LCM for multiple numbers?

a) By finding the LCM of two numbers at a time in a loop

b) By using brute force on all numbers

c) By multiplying all numbers directly

d) By computing the sum of all numbers and dividing by their count

10. Which real-world applications use LCM calculations?

a) Cryptography

b) Scheduling tasks in multithreading

c) Networking (packet synchronization)

d) All of the above

Also Read: Top 8 Reasons Why Java Is So Popular and Widely Used in 2025

You can continue expanding your skills in Java with upGrad, which will help you deepen your understanding of advanced Java concepts and real-world applications.

Upskill with upGrad to Keep Up With Industry Trends 

upGrad’s courses provide expert training on essential concepts like LCM computation, GCD optimization, and efficient number theory applications in Java. You’ll gain hands-on experience solving real-world problems involving LCM, from cryptography and scheduling to data synchronization.

Below are some relevant upGrad courses:

• Core Java Basics
• JavaScript Basics from Scratch
• Learn Basic Python Programming
• Data Structures & Algorithms
• AI-Powered Full Stack Development Course by IIITB

You can also get personalized career counseling with upGrad to guide your career path, or visit your nearest upGrad center and start hands-on training today! 

Similar Reads:

• Step by Step Java Tutorial Concepts - From Beginner to Pro
• What is Java? Java Programming Language Explained
• History of Java
• Java Tutorial for Beginners
• How Java Program Works?
• What is Java JDK? Java Development Kit
• C++ Vs Java: Choosing the Right Language for Your Project
• Difference between Python and Java
• Difference Between Java and JavaScript
• C++ Vs Java: Choosing the Right Language for Your Project
• Difference between Python and Java
• Difference Between Java and JavaScript
• From Java Source Code to Executable
• Java Installation on Linux: A Beginner-Friendly Guide
• Step-by-Step Guide: Installing Java on Windows 10
• Java Hello World Program: Your First Step into Java Programming

FAQs

1. Can LCM calculations be parallelized for better performance?

Yes, using parallel streams or Fork/Join framework can speed up LCM for multiple numbers. However, synchronization overhead should be managed carefully.

2. How do floating-point precision errors impact LCM in Java?

Floating-point (double, float) can cause rounding errors in LCM calculations. Always use integers (int, long) or BigInteger for accuracy.

3. What are the risks of using modulo operations in LCM calculations?

Using % incorrectly in LCM calculations can cause integer overflow. Always divide before multiplying to prevent errors.

4. How do I optimize LCM calculations for real-time applications?

Cache LCM values and use lookup tables (HashMap) for frequently used numbers. Parallel computation can also improve performance.

5. Can LCM be computed using bitwise operations?

Yes, Binary GCD Algorithm speeds up LCM by removing common factors using bitwise shifts (>>). It’s useful in low-level computing.

6. Why does LCM calculation sometimes slow down exponentially?

Redundant calculations occur when finding LCM of multiple numbers. Filter out multiples first and use stream distinct operations.

7. How do I handle LCM in multithreaded applications without deadlocks?

Avoid synchronized LCM calculations; use thread-safe structures like AtomicInteger. This prevents race conditions and deadlocks.

8. Why is division sometimes avoided when computing LCM?

Division is expensive in low-level systems, so subtraction-based methods can approximate LCM. This reduces expensive division operations.

9. How does LCM affect AI and Machine Learning computations?

LCM helps align batch processing and scheduling in ML training. It synchronizes datasets with different batch sizes for efficient computation.

10. Can LCM be precomputed for faster execution in competitive programming?

Yes, precompute and store LCM values in arrays to avoid recalculations. Dynamic programming also helps optimize sequential LCM calculations.

11. How does LCM help in cryptographic key generation?

In RSA encryption, LCM is used in Euler’s totient function for key generation. It ensures secure public and private key derivation.

Take the Free Quiz on Java

Answer quick questions and assess your Java knowledge

Start Quiz