Online Ethical Hacking Course

Apply Now

Examples

LCM of Two Numbers in Java (LCM Program and Code)

Efficiency and accuracy are highly important in programming and computer science. Whether you're an experienced developer or just starting your journey into coding, understanding fundamental mathematical concepts can greatly enhance your problem-solving capabilities. 

One such concept is the "Least Common Multiple" or LCM in Java.

The LCM is a vital mathematical tool used to find the smallest multiple that is evenly divisible by two or more integers. Mastering the art of finding the LCM of two numbers in Java is essential for tackling a wide range of computational problems. This tutorial will serve as your comprehensive guide to understanding LCM and implementing it effectively in Java.

Meaning of LCM

The LCM, or Least Common Multiple, of two or more numbers is the smallest positive integer that is divisible by all of those numbers without leaving a remainder. It's often denoted as LCM(a, b), where 'a' and 'b' are the two numbers whose LCM we want to find. 

Applications of LCM in Programming

This concept finds applications in various real-world scenarios, including:

  • Time Synchronization: LCM is used in computer science and telecommunications to synchronize processes or events. For example, when scheduling periodic tasks or events in a distributed system, you might need to determine when the next synchronization point should occur.

  • Fraction Operations: When working with fractions, finding the LCM of the denominators is crucial for performing addition, subtraction, or comparison operations.

  • Algorithm Design: LCM plays a significant role in designing efficient algorithms. For instance, it is employed in the Sieve of Eratosthenes algorithm for finding prime numbers.

  • Real-world Scheduling: In real-life scheduling problems like bus routes, flight schedules, or manufacturing processes, LCM can help optimize resource allocation and minimize conflicts.

This tutorial will provide you with a step-by-step breakdown of how to calculate the LCM of two numbers in Java, using both traditional and more efficient algorithms. 

Concepts to Learn:

LCM of Two Numbers in Java Using Brute Force Method

The brute force method for finding the LCM involves iterating through multiples of the larger number until we find a multiple that is also divisible by the smaller number. In the example below, we want to find the LCM of 12 and 18.

Code

public class LCMBruteForce {
    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        int lcm = findLCMBruteForce(num1, num2);
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + lcm);
    }

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

Output

LCM of 12 and 18 is 36

Explanation

  • We start with the larger number, which is 18.

  • We check if 18 is divisible by 12. If not, we increment 18 to 19 and continue checking until we find a number that is divisible by both 12 and 18.

  • In this case, we find that 36 is the smallest multiple of 18 that is also divisible by 12.

  • So, the LCM of 12 and 18 is 36, which is the value returned by the findLCMBruteForce method.

While this method is straightforward, it can be inefficient for large numbers, as it involves potentially testing a large number of multiples. There are more efficient algorithms, such as using the GCD, to find the LCM of two numbers.

Full Stack Developer Course

LCM Program in Java Using GCD

This method for finding the LCM of 2 numbers in Java uses the concept that the product of two numbers is equal to the product of their LCM and GCD (Greatest Common Divisor).

Code

public class LCMUsingGCD {
    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        int lcm = findLCMUsingGCD(num1, num2);
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + lcm);
    }

    public static int findLCMUsingGCD(int a, int b) {
        int gcd = findGCD(a, b);
        return (a * b) / gcd;
    }

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

Output

LCM of 12 and 18 is 36

Explanation

  • We start with two numbers, in this case, 12 and 18.

  • First, we find the GCD of the two numbers using the findGCD method. The GCD of 12 and 18 is calculated iteratively using the Euclidean algorithm. In this case, it is found to be 6.

  • Then, we use the formula: LCM(a, b) = (a * b) / GCD(a, b). So, LCM(12, 18) = (12 * 18) / 6 = 36.

  • The LCM of 12 and 18 is 36, which is the value returned by the findLCMUsingGCD method.

This method is more efficient than the brute force method as it relies on the GCD calculation, which is typically faster and requires fewer iterations, especially for larger numbers. It's a commonly used approach for finding the LCM of two numbers in Java.

LCM of Two Numbers in Java Using Formula

Below is a program on how to find LCM of two numbers in Java using the formula: LCM(a, b) = (a * b) / GCD(a, b)

Code

public class LCMUsingFormula {
    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        int lcm = findLCMUsingFormula(num1, num2);
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + lcm);
    }

    public static int findLCMUsingFormula(int a, int b) {
        int gcd = findGCD(a, b);
        return (a * b) / gcd;
    }

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

Output

LCM of 12 and 18 is 36

Explanation

This method for finding the LCM in Java directly applies the formula: LCM(a, b) = (a * b) / GCD(a, b), where GCD(a, b) represents the Greatest Common Divisor of 'a' and 'b'. 

Here's how it works:

  • We start with two numbers, in this case, 12 and 18.

  • First, we find the GCD of the two numbers using the findGCD method. The GCD of 12 and 18 is calculated iteratively using the Euclidean algorithm, and it is found to be 6.

  • Then, we use the formula: LCM(a, b) = (a * b) / GCD(a, b). So, LCM(12, 18) = (12 * 18) / 6 = 36.

  • The LCM of 12 and 18 is 36, which is the value returned by the findLCMUsingFormula method.

This method is both efficient and concise. It combines the GCD calculation with the LCM calculation using a simple formula. It is a commonly used approach for finding the LCM of two numbers in Java and is suitable for various programming scenarios.

Learn Next: