LCM of Two Numbers Explained

Problem Statement

Given two positive integers a and b, find their least common multiple (LCM). The LCM is the smallest positive integer that is divisible by both a and b. This can be computed using the formula LCM(a, b) = (a * b) / GCD(a, b), where GCD is the greatest common divisor.

Example

Input: a = 6, b = 8

Output: 24

Explanation: The multiples of 6 are 6, 12, 18, 24, ..., and of 8 are 8, 16, 24, .... The smallest common multiple is 24.

Code

public class Solution {
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.lcm(6, 8)); // 24
    }
}
            

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

# Example usage
print(lcm(6, 8))  # 24
            

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

// Example usage
console.log(lcm(6, 8)); // 24
            

Explanation

• Compute the GCD of a and b using Euclid’s algorithm.
• Use the formula LCM(a, b) = (a * b) / GCD(a, b).
• Perform integer division to avoid floating-point issues.
• Ensure inputs are positive to avoid undefined behavior.

Note