How To Find LCM Of Two Numbers In Java? Simplified With Examples

13 mins read

In the world of programming, understanding fundamental concepts like the Least Common Multiple (LCM) is crucial for building problem-solving skills. For college students just starting with Java, the concept of LCM might seem tricky at first, but once broken down, it becomes an easy and interesting challenge. 

In this article, we'll explore how to calculate the LCM of two numbers using Java, step-by-step. Whether you're preparing for exams or working on a coding assignment, this guide will help you understand the approach and code to solve LCM-related problems with ease. Let's dive into the basics and tackle this problem using simple, effective Java techniques!

Understanding The Concept Of LCM In Mathematics

The Least Common Multiple (LCM) is the smallest positive integer that is divisible by two or more given numbers. It represents the smallest multiple that the numbers share, making it a crucial concept in arithmetic, number theory, and practical problem-solving scenarios such as finding a common time interval, coordinating schedules, or solving problems involving fractions.

Properties Of LCM

Some of the common and important properties of LCM that are required in programming are as follows: 

• Commutativity: lcm(a, b) = lcm(b, a) The order of the numbers doesn't matter.
• Associativity: lcm(a, lcm(b, c)) = lcm(lcm(a, b), c) You can group the numbers in different ways.
• Identity: lcm(a, 1) = a The LCM of any number and 1 is the number itself.
• Zero: lcm(a, 0) = 0 The LCM of any number and 0 is 0 (except for the case where a is also 0, where it's undefined).
• If a divides b, then lcm(a, b) = b: If a is a factor of b, then the LCM is simply b.

We will now look at the different techniques to find the LCM of two numbers in Java programming.

Find LCM Of Two Numbers In Java Using The Brute-Force Method (While Loop And If Statement)

The brute-force method is a straightforward approach to find the Least Common Multiple (LCM) of two numbers. By using a while loop to iterate through potential multiples and if statements to check divisibility, this method identifies the smallest number divisible by both inputs. While simple, this method can be inefficient for larger numbers.

Algorithm For Finding LCM Using Brute-Force Method

1. Input: Two integers, a and b.
2. Initialize: Set a variable max to the larger of a and b. This will be our starting point for checking multiples.
3. While Loop: Continuously check if max is divisible by both a and b.
• If max % a == 0 and max % b == 0, then max is the LCM.
• Otherwise, increment max by 1 and repeat.
4. Output: Return the value of max as the LCM.

Code Example: 

public class LCMBruteForce {

    public static int findLCM(int a, int b) {
        // Start from the maximum of the two numbers
        int max = Math.max(a, b);

        // Loop until we find the LCM
        while (true) {
            if (max % a == 0 && max % b == 0) {
                return max; // LCM found
            }
            max++; // Increment to check the next number
        }
    }

    public static void main(String[] args) {
        // Example input
        int num1 = 12, num2 = 18;

        // Find and display the LCM
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + findLCM(num1, num2));
    }
}

Output (set the code file name as LCMBruteForce.java): 

LCM of 12 and 18 is: 36

Explanation: 

In the above code example-

1. We start by defining a class LCMBruteForce to encapsulate our logic for finding the Least Common Multiple (LCM) using the brute-force approach.
2. The method findLCM(int a, int b) is where the calculation takes place.
3. Inside this method, we initialize a variable max to the larger of the two numbers, a and b, using Math.max(a, b). This gives us a reasonable starting point since the LCM cannot be smaller than the larger number.
4. Next, we enter a while loop that runs indefinitely until we find a number divisible by both a and b.
5. At each iteration, we check if the current value of max is divisible by both numbers using the condition max % a == 0 && max % b == 0.
• If the condition is true, we return max, as it satisfies the properties of the LCM.
• If not, we increment max by 1 and continue checking.
6. In the main() method, we test our implementation using two example numbers, 12 and 18.
7. We call findLCM(num1, num2) to compute the LCM and display the result using System.out.println().
8. The program prints the message: LCM of 12 and 18 is: 36, demonstrating that the logic works as intended.

Explore this amazing course and master all the key concepts of Java programming effortlessly!

Find LCM Of Two Numbers In Java Using GCD (Greatest Common Divisor)

The GCD-based method is an efficient way to calculate the Least Common Multiple (LCM) by using the mathematical relationship between LCM and GCD. This method uses the formula:

LCM(𝑎,𝑏) = |𝑎*𝑏| / GCD(𝑎,𝑏)

Here, the GCD is calculated using the Euclidean algorithm, making this approach faster and more suitable for large numbers.

Algorithm for Finding LCM Using GCD

1. Input: Two integers, a and b.
2. Calculate GCD:Use the Euclidean algorithm to find the GCD of a and b.
• While b is not 0, set a = b and b = a % b.
• When b becomes 0, a is the GCD.
3. Calculate LCM: Use the formula: LCM(𝑎,𝑏) = |𝑎*𝑏| / GCD(𝑎,𝑏)
4. Output: Return the calculated LCM.

Code Example: 

public class LCMUsingGCD {

    // Function to calculate 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 calculate LCM using GCD
    public static int findLCM(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        // Example input
        int num1 = 12, num2 = 18;

        // Find and display the LCM
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + findLCM(num1, num2));
    }
}

Output (set the code file name as LCMUsingGCD.java): 

LCM of 12 and 18 is: 36

Explanation: 

In the above code example-

1. We begin by defining a class LCMUsingGCD to handle the logic for finding the Least Common Multiple (LCM) using the Greatest Common Divisor (GCD).
2. Inside the class, we create a method gcd(int a, int b) that calculates the GCD of two numbers using the Euclidean algorithm.
3. In the gcd method, we use a while loop that continues to execute as long as b is not zero.
4. Within each iteration of the loop, we store the current value of b in a temporary variable temp.
5. We then update b to be the remainder of a divided by b using a % b, effectively applying the Euclidean algorithm step.
6. Now we set a to the value of temp, preparing for the next iteration to continue finding the GCD.
7. Once b becomes zero, the loop terminates, and we return a as the GCD of the original two numbers.
8. Next, we define the method findLCM(int a, int b) which calculates the LCM by using the formula (a * b) / gcd(a, b), leveraging the previously defined gcd method.
9. In the main() method, we provide example inputs by initializing two integers, num1 and num2, with the values 12 and 18 respectively.
10. We call the findLCM(num1, num2) method to compute the LCM of these two numbers.
11. Finally, we display the result using System.out.println(), which outputs the message: LCM of 12 and 18 is: 36, demonstrating that our implementation correctly calculates the LCM using the GCD method.

Sharpen your coding skills with Unstop's 100-Day Coding Sprint and compete now for a top spot on the leaderboard!

Find LCM Of Two Numbers Using Prime Factorization In Java

The prime factorization method involves breaking down both numbers into their prime factors and combining these factors to compute the LCM. This approach uses the concept of taking the highest power of each prime factor found in the numbers to calculate the LCM

Algorithm For Finding LCM Using Prime Factorization

1. Input: Two integers, a and b.
2. Find Prime Factors:
• Decompose both numbers into their prime factors.
• Count the occurrences of each prime factor.
3. Combine Factors:
• For each unique prime factor, take the highest power found in the two numbers.
• Multiply these factors together to compute the LCM.
4. Output: Return the result as the LCM.

Code Example: 

import java.util.HashMap;
import java.util.Map;

public class LCMPrimeFactorization {

    // Function to find prime factors of a number
    public static Map<Integer, Integer> getPrimeFactors(int num) {
        Map<Integer, Integer> factors = new HashMap<>();
        for (int i = 2; i <= num; i++) {
            while (num % i == 0) {
                factors.put(i, factors.getOrDefault(i, 0) + 1);
                num /= i;
            }
        }
        return factors;
    }

    // Function to find LCM using prime factorization
    public static int findLCM(int a, int b) {
        Map<Integer, Integer> factorsA = getPrimeFactors(a);
        Map<Integer, Integer> factorsB = getPrimeFactors(b);

        // Combine factors by taking the maximum power of each prime
        Map<Integer, Integer> lcmFactors = new HashMap<>(factorsA);
        for (Map.Entry<Integer, Integer> entry : factorsB.entrySet()) {
            lcmFactors.put(entry.getKey(),
                Math.max(lcmFactors.getOrDefault(entry.getKey(), 0), entry.getValue()));
        }

        // Calculate LCM by multiplying prime factors with their powers
        int lcm = 1;
        for (Map.Entry<Integer, Integer> entry : lcmFactors.entrySet()) {
            lcm *= Math.pow(entry.getKey(), entry.getValue());
        }
        return lcm;
    }

    public static void main(String[] args) {
        // Example input
        int num1 = 12, num2 = 18;

        // Find and display the LCM
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + findLCM(num1, num2));
    }
}

Output (set the code file name as LCMPrimeFactorization.java): 

LCM of 12 and 18 is: 36

Explanation: 

In the above code example-

1. We define a class LCMPrimeFactorization to calculate the Least Common Multiple (LCM) using the prime factorization method.
2. The getPrimeFactors(int num) method is responsible for finding the prime factors of a given number along with their powers.
3. Inside this method, we use a HashMap to store each prime factor as a key and its corresponding power as the value.
4. We iterate through all numbers starting from 2 up to num, and for each number i, we check if it divides num.
5. If it does, we add i to the map or update its count using factors.getOrDefault(i, 0) + 1 and divide num by i repeatedly until num is no longer divisible by i.
6. Once all prime factors and their powers are recorded, we return the map.
7. The findLCM(int a, int b) method calculates the LCM using the prime factors of a and b.
8. We call getPrimeFactors for both numbers to get their prime factor maps.
9. We then create a new map lcmFactors to store the combined prime factors, ensuring we take the maximum power of each prime factor between the two numbers.
10. To achieve this, we iterate through the prime factors of b and update lcmFactors using Math.max to take the higher power for each prime.
11. Once the combined prime factor map is ready, we calculate the LCM by multiplying each prime factor raised to its respective power using Math.pow.
12. In the main() method, we test our implementation with two example numbers, 12 and 18.
13. We call findLCM(num1, num2) to compute the LCM and display the result using System.out.println().
14. The program outputs: LCM of 12 and 18 is: 36, showing that the prime factorization method correctly computes the LCM.

Real-World Applications Of Finding LCM Of Two Numbers In Java

The concept of Least Common Multiple (LCM) is widely applicable in various real-world scenarios. Here's how finding LCM can be practically useful:

• Scheduling Problems

• Scenario: Suppose two events repeat after different intervals (e.g., one every 6 days and another every 8 days). The LCM helps determine when both events will occur on the same day.
• Java Application: Automating scheduling tasks in event planners or calendars.
1. Signal Processing
• Scenario: In systems where multiple signals with different frequencies need to be synchronized, the LCM is used to find the lowest time period for signal alignment.
• Java Application: Used in digital signal processing software to manage sampling rates.
2. Traffic Light Systems
• Scenario: Traffic lights at an intersection operate at different cycle times (e.g., 45 seconds and 60 seconds). The LCM helps calculate when all lights will reset to their original state simultaneously.
• Java Application: Used in traffic simulation software to optimize signal timings.
3. Data Synchronization
• Scenario: In distributed systems or networks, tasks with different execution periods need to be synchronized. The LCM is used to determine the next point of synchronization.
• Java Application: Used in task schedulers and distributed computing systems.
4. Gear Mechanics
• Scenario: Two gears with different numbers of teeth will realign after a certain number of rotations. The LCM helps calculate when the gears return to their starting positions.
• Java Application: Useful in simulations for designing mechanical systems.
5. Music and Rhythm Patterns
• Scenario: In musical compositions, rhythms with different beat intervals can be synchronized using the LCM to determine when they repeat in harmony.
• Java Application: Applied in music software for composing and syncing beats.
6. Classroom Activities
• Scenario: Two students are tasked to meet after certain intervals of days (e.g., one after 3 days and the other after 5 days). The LCM tells when they'll meet again.
• Java Application: Useful in educational apps for solving math problems interactively.

Are you looking for someone to answer all your programming-related queries? Let's find the perfect mentor here.

Conclusion

In this article, we've explored various methods to find the Least Common Multiple (LCM) of two numbers in Java. From the brute-force method, which iterates through multiples to find the LCM, to more efficient approaches like using GCD (Greatest Common Divisor), each method offers its own strengths and weaknesses. The prime factorization method, although computationally intensive, helps us understand the role of prime factors in determining the LCM.

Understanding and implementing LCM calculation not only deepens our grasp of mathematical concepts but also enhances our problem-solving skills, especially in real-world scenarios like scheduling, signal processing, and synchronization tasks. By leveraging Java's capabilities, we can efficiently solve these types of problems in applications ranging from traffic light systems to complex data synchronization in distributed systems.

Ultimately, knowing how to compute LCM opens the door to solving a variety of practical problems in software development, making it an essential concept for both beginners and advanced programmers.

Frequently Asked Questions

Q. What is the Least Common Multiple (LCM) of two numbers?

The Least Common Multiple (LCM) of two numbers is the smallest positive integer that is divisible by both numbers. For example, the LCM of 12 and 18 is 36 because 36 is the smallest number that both 12 and 18 can divide evenly into.

In Java, the LCM can be found using various methods such as brute-force, GCD-based approaches, and prime factorization.

Q. How do I calculate the LCM of two numbers using the brute-force method in Java?

In the brute-force method, we start by choosing the larger of the two numbers as the candidate for the LCM. Then, we increment this candidate by 1 in each iteration and check if it is divisible by both numbers. The first value that meets this condition is the LCM.

Here’s a quick example:

public static int findLCM(int a, int b) {
    int max = Math.max(a, b);  // Start with the larger number
    while (true) {
        if (max % a == 0 && max % b == 0) {  // Check if max is divisible by both a and b
            return max;  // Return the LCM
        }
        max++;  // Increment max until LCM is found
    }
}

This method is easy to understand but inefficient for large numbers because it checks each number incrementally.

Q. How is the LCM related to the Greatest Common Divisor (GCD)?

The relationship between LCM and GCD is given by the following formula:

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

In this formula:

• GCD is the greatest common divisor, which is the largest number that divides both a and b without leaving a remainder.
• LCM can be efficiently calculated using the GCD because the product of the two numbers divided by their GCD gives the least common multiple.

For example, to calculate the LCM of 12 and 18, we first find the GCD, which is 6, and then use the formula to get:

LCM(12,18) = (12×18)/6 = 36

Q. Why is the prime factorization method not commonly used to find LCM?

While the prime factorization method works by decomposing both numbers into their prime factors and then using the highest powers of each prime factor to find the LCM, it is generally not as efficient as methods like the GCD-based approach.

Prime factorization requires more computational resources as you must factorize both numbers, which can take longer for large numbers. The method can be insightful for educational purposes but is not ideal for real-time or large-scale applications.

Q. What is the time complexity of finding the LCM using the brute-force method in Java?

The time complexity of the brute-force method is O(L), where L is the Least Common Multiple of the two numbers a and b. This is because we increment the candidate value (starting from the larger of the two numbers) by 1 in each iteration until we find the LCM, which can take up to the value of the LCM.

For larger values of a and b, the brute-force method becomes inefficient compared to other approacheslike using the GCD-based method, which has a time complexity of O(log(min(a, b))).

Q. Can LCM be used in real-world applications, and if so, how?

Yes, the concept of LCM is applied in various real-world scenarios such as:

• Scheduling Events: For example, if two events occur every 6 and 8 days, finding the LCM helps determine when both events will occur on the same day.
• Signal Synchronization: In telecommunications, LCM is used to synchronize signals with different frequencies to ensure they align at the same time.
• Traffic Light Systems: In traffic control, LCM is used to determine when traffic lights at an intersection will all reset to their initial states at the same time.

By using the LCM, these problems can be solved efficiently, especially when working with systems that require synchronization or alignment of periodic tasks.

With this, we conclude our discussion on how to find lcm of two numbers in Java. Here are a few other topics that you might be interested in reading: 

1. 15 Popular JAVA Frameworks Use In 2023
2. What Is Scalability Testing? How Do You Test Application Scalability?
3. Top 50+ Java Collections Interview Questions
4. 10 Best Books On Java In 2024 For Successful Coders
5. Difference Between Java And JavaScript Explained In Detail
6. Top 15+ Difference Between C++ And Java Explained! (+Similarities)