Java Program to Find LCM of Two Numbers

Java Program to Find LCM of Two Numbers | We have developed many Java programs related to flow control statements. Now in this post, we will develop a Java program to find the lcm of two numbers.

Least or lowest common multiple (LCM) of two integers a and b is the smallest positive number that is divisible by both a and b. Example:- LCM of 12 and 15 is 60 because 60 is divisible by both 12 and 15.Java Program to Find LCM of Two Numbers

Procedure to find the lcm of two numbers,
1) Take two numbers
2) Find the smallest and largest number among them
3) Take a temporary variable minMultiple
4) Initialize minMultiple with the smallest number
5) Divide variable minMultiple by largest Number
6) If it is divisible by the largest number then it is the lcm of both numbers
7) Else increase the minMultiple variable with the smallest number
8) Repeat 5 to 7 process until getting the result

We are increasing minMultiple by the smallest number so, no need to check minMultiple is divisible by the smallest number or not, it will always divisible by smallestNumber.

import java.util.Scanner;

public class LCMProgram {

  public static long findLCM(int n1, int n2) {
     // declare temporary variable to store lcm
     long minMultiple = 0;

     // find smallest and largest number 
     int smallest = (n1<n2) ? n1 : n2;
     int largest = (n1>n2) ? n1 : n2;

     // assign smallest number to minMultiple
     minMultiple = smallest;

     // loop
     while(true) {
        if(minMultiple % largest == 0)
            return minMultiple;
        minMultiple = minMultiple + smallest ;
     }
  }

  public static void main(String[] args) {

     // declare variables
     int number1 = 0;
     int number2 = 0;
     long lcm = 0;

     // create Scanner class object 
     Scanner scan = new Scanner(System.in);

     // take input
     System.out.print("Enter two integer numbers::");
     number1 = scan.nextInt();
     number2 = scan.nextInt();

     // find LCM of both numbers
     lcm = findLCM(number1, number2);

     // display LCM value
     System.out.println("LCM(" + number1
           + "," + number2 + ") = " + lcm );

     // close Scanner class object
     scan.close();
  }
}

The output for different test-cases:

Enter two integer numbers:: 12 15
LCM(12,15) = 60

Enter two integer numbers:: 3 4
LCM(3,4) = 12

Example of execution process:-

Enter two integer numbers:: 12 15
Smallest number = 12
Largest number = 15
minMultiple = 12

Iteration 1,
12%15 != 0
minMultiple =12+12
minMultiple = 24

Iteration 2,
24%15 != 0
minMultiple =24+12
minMultiple = 36

Iteration 3,
36%15 != 0
minMultiple =36+12
minMultiple = 48

Iteration 4,
48%15 != 0
minMultiple =48+12
minMultiple = 60

Iteration 5,
60%15 == 0
LCM(12,15) = 60

Java Program to Find LCM of two numbers using HCF

The product of two numbers a and b is equal to the product of HCF(a,b) and LCM(a,b).

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

The HCF ( highest common factor ) is also referred also as GCD ( Greatest Common Measure ), Using this formula we can find GCD and LCM at a time. We need to find either GCD and LCM and then apply this formula.

In the below program to find LCM of two numbers in java; First, we find the HCF then using formula LCM will be calculated. The Formula used for this purpose is:-

LCM(a,b) = (a*b) / HCF(a,b)
import java.util.Scanner;

public class LCMProgramUsingHCF {

  private static int findHCF(int num1, int num2) {
     while(num1 != num2) {
        if(num1 > num2) 
           num1 = num1 - num2;
        else
           num2 = num2 - num1;
     }
     return num1;
  }

  // LCM(n1,n2) = ( n1*n2 ) / HCF(n1,n2)
  public static long findLCM(int num1, int num2){
     return (num1*num2) / findHCF(num1, num2);
  }

  public static void main(String[] args) {

     // declare variables
     int number1 = 0;
     int number2 = 0;
     long lcm = 0;

     // create Scanner class object 
     Scanner scan = new Scanner(System.in);

     // take input
     System.out.print("Enter two integer numbers::");
     number1 = scan.nextInt();
     number2 = scan.nextInt();

     // find LCM of both numbers
     lcm = findLCM(number1, number2);

     // display LCM value
     System.out.println("LCM(" + number1
              + "," + number2 + ") = " + lcm );

     // close Scanner class object
     scan.close();
  }
}

LCM using recursion

We can also use the recursion technique to find the lcm of two numbers. A technique of defining the method/function that contains a call to itself is called the recursion. The recursive function/method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

import java.util.Scanner;
public class LCMProgramUsingRecursion {
  private static int common;

  public static long findLCM(int n1, int n2) {
     // increase common
     common += n2;
     if(common % n1 == 0)
         return common; // base case
     else 
         return findLCM(n1, n2); //general case
  }

  public static void main(String[] args) {

     // declare variables
     int number1 = 0;
     int number2 = 0;
     long lcm = 0;

     // create Scanner class object 
     Scanner scan = new Scanner(System.in);

     // take input
     System.out.print("Enter two integer numbers::");
     number1 = scan.nextInt();
     number2 = scan.nextInt();

     // find LCM of both numbers
     lcm = findLCM(number1, number2);

     // display LCM value
     System.out.println("LCM(" + number1
            + "," + number2 + ") = " + lcm );

     // close Scanner class object
     scan.close();
  }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or you find anything incorrect? Let us know in the comments. Thank you!

Leave a Reply