Finding LCM of two numbers in java and Python – Two Approaches with Code & Optimization Techniques

🚀 Introduction

In this post, I'll explore different methods to calculate the Least Common Multiple (LCM) of two numbers, comparing a brute-force approach with a mathematical optimization using GCD. This is essential knowledge for developers working with fractions, scheduling algorithms, or periodic computations.

🧠 Problem Statement / Objective

Implement two approaches to find LCM of two integers:

1. Brute-force method checking multiples

2. Mathematical method using GCD formula (LCM = (a*b)/GCD(a,b))
   Provide implementations in both Java and Python with test cases.

🧩 Tools & Technologies Used

• Languages: Java, Python

• Algorithms: Euclidean Algorithm (for GCD), LCM calculation

• Concepts: Mathematical optimization, Brute-force vs efficient solutions

💻 Java Code

package maths;

public class Lcm {

    // Brute-force approach
    private static int lcm(int a, int b) {
        int max = Math.max(a, b);
        int result = a * b;
        for (int i = max; i < result; i++) {
            if (i % a == 0 && i % b == 0) {
                result = i;
                break;
            }
        }
        return result;
    }

    // GCD using Euclidean algorithm
    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    // Optimized LCM using GCD
    public static int bestSolutionToFindLCM(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        // Test brute-force method
        System.out.println(lcm(60, 36));     // Output: 180
        System.out.println(lcm(10, 5));      // Output: 10
        System.out.println(lcm(8, 12));      // Output: 24
        System.out.println(lcm(100, 25));    // Output: 100
        System.out.println(lcm(81, 27));     // Output: 81

        // Test optimized method
        System.out.println(bestSolutionToFindLCM(60, 36));  // Output: 180
        System.out.println(bestSolutionToFindLCM(10, 5));   // Output: 10
        System.out.println(bestSolutionToFindLCM(8, 12));   // Output: 24
        System.out.println(bestSolutionToFindLCM(100, 25)); // Output: 100
        System.out.println(bestSolutionToFindLCM(81, 27));  // Output: 81
    }
}

💻 Python Code

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm_brute_force(a, b):
    max_val = max(a, b)
    result = a * b
    for i in range(max_val, result):
        if i % a == 0 and i % b == 0:
            result = i
            break
    return result

def lcm_optimized(a, b):
    return (a * b) // gcd(a, b)

# Test cases
test_numbers = [(60, 36), (10, 5), (8, 12), (100, 25), (81, 27)]

print("Brute-force method:")
for a, b in test_numbers:
    print(f"LCM of {a} and {b} is {lcm_brute_force(a, b)}")

print("\nOptimized method:")
for a, b in test_numbers:
    print(f"LCM of {a} and {b} is {lcm_optimized(a, b)}")

📘 Explanation

Brute-Force Approach:

1. Starts checking from the larger number up to a*b

2. Finds the first number divisible by both inputs

3. Inefficient for large numbers (O(n) time complexity)

Optimized Approach (using GCD):

1. Uses mathematical relationship: LCM(a,b) = (a × b)/GCD(a,b)

2. GCD calculated efficiently via Euclidean algorithm

3. Time complexity: O(log(min(a,b))) - much faster for large numbers

Key Differences:

• The brute-force method can be slow for large numbers (e.g., 10,000+)

• The GCD-based method is consistently fast regardless of input size

• Both methods handle negative numbers similarly (absolute values are considered)

🛠️ Output / Result

Both implementations will produce:

180
10
24
100
81

(for both methods)

📌 Real-World Use Cases

1. Fraction Arithmetic: Adding/subtracting fractions with different denominators

2. Scheduling: Finding when periodic events will coincide

3. Digital Signal Processing: Determining sample rate conversions

4. Cryptography: In RSA algorithm implementations

5. Game Development: Calculating sprite animation frame timing

🧵 Conclusion

Key takeaways:

• The GCD-based method is significantly more efficient

• Mathematical insights can dramatically improve algorithm performance

• The same mathematical principles apply across programming languages

• Always consider edge cases (zero, negative numbers, etc.)