Java Code Example: Least Common Multiple (LCM)

The Least Common Multiple (LCM) of two numbers is the smallest number that is evenly 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 divide without a remainder.

Formula to Compute LCM

The LCM of two numbers can be found using their Greatest Common Divisor (GCD):

Using this formula, we can compute the LCM efficiently by first finding the GCD and then applying the formula.

Java Code Example

public class LCMCalculator {
    // Method to find the GCD using Euclidean Algorithm (Recursive)
    public static int findGCD(int a, int b) {
        if (b == 0) {
            return a; // Base case: when b becomes zero, return a
        }
        return findGCD(b, a % b); // Recursive case: call GCD with (b, remainder of a/b)
    }

    // Method to calculate LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b)
    public static int findLCM(int a, int b) {
        return (a * b) / findGCD(a, b);
    }

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

Output

LCM of 12 and 18 is: 36

Explanation

1. Finding GCD:
   • We use the Euclidean Algorithm to find the GCD of the two numbers.
   • findGCD(12, 18) → findGCD(18, 12) → findGCD(12, 6) → findGCD(6, 0) → GCD = 6.
2. Applying LCM Formula:
   • Using the formula LCM(a, b) = (a * b) / GCD(a, b).
   • LCM(12, 18) = (12 * 18) / 6 = 216 / 6 = 36.
3. Returning the LCM:
   • The result is printed as 36, which is the smallest multiple of both 12 and 18.

Key Takeaways

✅ Efficient Calculation – Uses GCD for optimized computation.
✅ Mathematical Foundation – Based on the fundamental properties of numbers.
✅ Useful in Real-world Applications – Scheduling problems, fraction operations, cryptography.