LCM of two Numbers in Java

In this article, we will look at how to find the LCM of two numbers in Java using multiple methods. In the end, we will also compare the performance of all the methods.

LCM of two numbers is the smallest number that is divisible by both numbers. For example, the LCM of 3 and 4 is 12 because 12 is the smallest number that is divisible by both 3 and 4.

LCM stands for Least Common Multiple.

To find the LCM of two numbers, find all the prime factors of both the numbers, take their union and multiply them. You will have the LCM of the two numbers.

LCM of two numbers
LCM of 2 numbers

LCM of two numbers can also be found by using the formula LCM(a, b) = (a * b) / GCD(a, b). Here, GCD stands for Greatest Common Divisor.

Method 1

The first idea to find LCM is to check for all numbers starting from 1 and find the first number that is divisible by both the numbers. This is the LCM of the two numbers.

Optimize this by following the below steps:

  1. Start with the maximum of the two numbers. This will reduce the number of iterations.
  2. Start jumping by a step of the maximum of the two numbers (because LCM will always be multiple of maximum). This will reduce the number of iterations by a huge amount.
import java.util.Scanner;

public class findLCM {
  static void lcm(int a, int b) {
    int lcm = 0;
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    for (int i = max; i <= a * b; i += max) {
      if (i % min == 0) {
        lcm = i;
        break;
      }
    }
    System.out.println("LCM of " + a + " and " + b + " is " + lcm);
  }

  public static void main(String args[]) {
    // find LCM of 2 numbers
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter 2 numbers:");
    int a = sc.nextInt();
    int b = sc.nextInt();
    lcm(a, b);

    sc.close();
  }
}

Output:

Enter 2 numbers:
12
18
LCM of 12 and 18 is 36

Method 2 ⭐️⭐️

Here is a better idea than the previous one. This can find the LCM of two numbers faster than the previous method but it is bit complex.

Idea is to find all the prime factors of both numbers using a loop and multiply them together. This will give the LCM of the two numbers.

Algorithm:

  1. Execute a loop that starts from 2 to half of the minimum of the two numbers.
  2. Check if the number is the prime factor of both numbers. Then divide both the numbers by the number and multiply the number with the 'lcm' variable.
  3. Repeat the above steps until both the numbers are not a factor of both the numbers.
  4. Finally, multiply the 'lcm' variable with the product of both numbers.
import java.util.Scanner;

public class findLCM {
  static void lcm(int a, int b) {
    int min = Math.min(a, b);
    int lcm = 1;

    for (int i = 2; i <= min / 2 + 1; i++) {
      while (a % i == 0 && b % i == 0) {
        lcm *= i;
        a /= i;
        b /= i;
      }
    }
    lcm = lcm * a * b;
    System.out.println("LCM of " + a + " and " + b + " is " + lcm);
  }

  public static void main(String args[]) {
    // find LCM of 2 numbers
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter 2 numbers:");
    int a = sc.nextInt();
    int b = sc.nextInt();
    lcm(a, b);

    sc.close();
  }
}

Output:

Enter 2 numbers:
98
54
LCM of 98 and 54 is 2646

Method 3 ⭐️⭐️⭐️

The third idea to find LCM of 2 number is to use the fact that LCM(a, b) = (a * b) / GCD(a, b).

So, first we will find the GCD of the two numbers and then divide the product of the two numbers by the GCD.

import java.util.Scanner;

public class findLCM {
  static int gcd(int a, int b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }

  static void lcm(int a, int b) {
    int lcm = (a * b) / gcd(a, b);
    System.out.println("LCM of " + a + " and " + b + " is " + lcm);
  }

  public static void main(String args[]) {
    // find LCM of 2 numbers
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter 2 numbers:");
    int a = sc.nextInt();
    int b = sc.nextInt();
    lcm(a, b);

    sc.close();
  }
}

Output:

Enter 2 numbers:
45
35
LCM of 45 and 35 is 315

Performance Comparison

Let's compare which of the above methods is the fastest.

For this, we will use the System.nanoTime() method to find the time taken by each method to find the LCM of two numbers.

import java.util.Scanner;

public class performance {
  static void method1(int a, int b) {
    int lcm = 0;
    int max = Math.max(a, b);
    int min = Math.min(a, b);
    for (int i = max; i <= a * b; i += max) {
      if (i % min == 0) {
        lcm = i;
        break;
      }
    }
  }

  static void method2(int a, int b) {
    int min = Math.min(a, b);
    int lcm = 1;

    for (int i = 2; i <= min / 2 + 1; i++) {
      while (a % i == 0 && b % i == 0) {
        lcm *= i;
        a /= i;
        b /= i;
      }
    }
    lcm = lcm * a * b;
  }

  static int gcd(int a, int b) {
    if (b == 0)
      return a;
    else
      return gcd(b, a % b);
  }

  static void method3(int a, int b) {
    int lcm = (a * b) / gcd(a, b);
  }

  public static void main(String args[]) {
    // check performance of all the methods
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter 2 numbers:");
    int a = sc.nextInt();
    int b = sc.nextInt();

    long start = System.nanoTime();
    method1(a, b);
    long end = System.nanoTime();
    System.out.println("Time taken by method 1: " + (end - start) + " ns");

    start = System.nanoTime();
    method2(a, b);
    end = System.nanoTime();
    System.out.println("Time taken by method 2: " + (end - start) + " ns");

    start = System.nanoTime();
    method3(a, b);
    end = System.nanoTime();
    System.out.println("Time taken by method 3: " + (end - start) + " ns");

    sc.close();
  }
}

Output:

java lcm performance output

From the above result, you can see method 3 is the fastest method.