Program to Find the Least Common Multiple (LCM) in Java

Least Common Multiple (LCM)

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.

We will explore three different methods to find the LCM of two numbers using Java programming.

Method 1: Using HCF

The LCM of two numbers can be calculated using the formula:

LCM(a, b) = (a * b) / HCF(a, b)

import java.util.Scanner;

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

    public static int findLCM(int a, int b) {
        return (a * b) / findHCF(a, b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + findLCM(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36

Method 2: Using Iteration

We start from the maximum of the two numbers and keep increasing until we find a number that is divisible by both.

import java.util.Scanner;

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

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + findLCM(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36

Method 3: Using Recursion

We use recursion to find the LCM by incrementing multiples of the larger number until we find a common multiple.

import java.util.Scanner;

public class LCMUsingRecursion {
    public static int findLCMRecursive(int a, int b, int multiple) {
        if (multiple % a == 0 && multiple % b == 0) {
            return multiple;
        }
        return findLCMRecursive(a, b, multiple + 1);
    }

    public static int findLCM(int a, int b) {
        return findLCMRecursive(a, b, Math.max(a, b));
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("LCM of " + num1 + " and " + num2 + " is " + findLCM(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 12
Enter second number: 18
LCM of 12 and 18 is 36