Java Program to Find the LCM of Two Numbers

Last Updated on May 17, 2023 by Prepbytes

The lowest number which is a multiple of all the supplied numbers is known as the Least Common Multiple or LCM, of a collection of integers in mathematics. In Java, there are a variety of techniques you may use to get the LCM of two numbers, including the "if condition," "while loop," and GCD method, among others.

What is the LCM of Two Numbers in Java?

The LCM, or least common multiple, is a method for determining the smaller of two numbers (n1 and n2) that may be divided by the given numbers. A number that is included in both numbers is known as a common multiple. The LCM of two integers is shown as LCM (a, b) or lcm (a, b).

Algorithm of the LCM of Two Numbers

• Step 1: Take two inputs from the user n1 and n2
• Step 2: Store the smallest common multiple of n1 and n2 into the max variable.
• Step 3: Validate whether the max variable is divisible by n1 and n2, and print the max as the LCM of two numbers.
• Step 4: Otherwise, the max value is updated by 1 on every iteration, and jump to step 3 to check the divisibility of the max variable.
• Step 5: Terminate the program

Methods to Find LCM of Two Numbers in Java

Below are discussed some methods to find LCM of two numbers in Java:

Method 1 to Find LCM of Two Numbers Using If Statement

By taking the first lowest number that is divisible by both a and b, we may get the LCM of two numbers a and b. Using the if condition, we may initialize the max_num variable with maximum(a, b), then increase max_num by 1 until max_num is divisible by both a and b.

Code Implementation

public class Main {
  public static void main(String[] args) {

    int n1 = 72, n2 = 120, lcm;

    // maximum number between n1 and n2 is stored in lcm
    lcm = (n1 > n2) ? n1 : n2;

    // Always true
    while(true) {
      if( lcm % n1 == 0 && lcm % n2 == 0 ) {
        System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
        break;
      }
      ++lcm;
    }
  }
}

Output

The LCM of 72 and 120 is 360

Time Complexity:
O(ab) as the while loop will run till it reaches the least common multiple of a and b. For example, 13 and 7 are the prime numbers whose LCM is 91. Here the loop starts from max(13,7)= 13 and ends at 91. Hence, the time complexity is found to be O(ab).

Space Complexity:
O(1) extra space is required as we are using int to save the previously calculated result.

Method 2 to Find LCM of Two Numbers using GCD (While Loop)

In mathematics, we are aware that the sum of the products of the two integers a and b themselves is equal to their Least Common Multiple (LCM) and Greatest Common Divisor (GCD).

LCM(a,b)∗GCD(a,b)=a∗b

Deducing the above statement:

‘LCM(a,b)=a∗b/GCD(a,b)‘

By using a while loop to calculate GCD(a, b) and dividing the sum of a and b by GCD(a, b), we may determine the LCM of two integers, a and b. The Euclidean algorithm may be used to compute the GCD(a, b) by subtracting the smaller number from the bigger one between a and b until both values are equal. GCD(a, b) is the number that was discovered after the while loop was terminated. Let’s use the examples of a = 14 and b = 35.

• Iteration 1: We subtract a from b: a = 14 and b = 35-14= 21.
• Iteration 2: We subtract a from b again as a< b: a = 14 and b = 21-14= 7.
• Iteration 3: We subtract b from an as a>b: a = 14-7= 7 and b = 7 We got a = b = 7. Therefore, GCD( 14, 35 )= 7

Code Implementation

public class Main {
  public static void main(String[] args) {

    int n1 = 72, n2 = 120, gcd = 1;

    for(int i = 1; i <= n1 && i <= n2; ++i) {
      // Checks if i is factor of both integers
      if(n1 % i == 0 && n2 % i == 0)
        gcd = i;
    }

    int lcm = (n1 * n2) / gcd;
    System.out.printf("The LCM of %d and %d is %d.", n1, n2, lcm);
  }
}

Output:

The LCM of 72 and 120 is 360

Time Complexity:
O(max(a, b)): As we know that in each iteration, we are subtracting either a from b or b from a. Hence, we can say max(a, b) iterations will give us the GCD of a and b.

Space Complexity:
O(1) extra space is required as we are using int to save the previously calculated result.

Method 3 to Find the LCM of Two Numbers Using GCD (Recursion)

We can find the LCM of two numbers a and b by using the formula:

LCM(a,b)=a∗b/GCD(a,b)

By subtracting the smaller number from the bigger number between a and b and then recursively sending a and b to the same function, we can use the Euclidean method to get the GCD of a and b.

Code Implementation

import java.util.*;    
class LcmExample2  
{  
//driver code  
public static void main(String args[])  
{  
int x, y;      
Scanner sc = new Scanner(System.in);    
System.out.print("Enter the first number: ");    
x = sc.nextInt();    
System.out.print("Enter the second number: ");   
y = sc.nextInt();    
System.out.println("LCM of " + x +" and " + y +" is " + findLcm(x, y));  
}  
//function that finds GCD of the number  
static int findGcd(int x, int y)  
{  
if (x == 0)  
//returns y is x==0  
return y;  
//calling function that returns GCD  
return findGcd(y % x, x);  
}  
//function finds the LCM  
static int findLcm(int x, int y)  
{  
//returns the LCM      
return (x / findGcd(x, y)) * y;  
}  
}

Output:

The LCM of 72 and 120 is 360

Time Complexity:
O(max(a, b)): As we know that in each recursive call, we are subtracting either a from b or b from a. Hence, we can say max(a, b) iterations will give us the GCD of a and b.

Space Complexity:
O(max(a, b)) extra space is required as total recursive calls are equal to the number of iterations until we get the GCD of the two numbers a and b.

Conclusion
In conclusion, the LCM (Least Common Multiple) is a fundamental mathematical concept used to find the smallest multiple that is divisible by two or more numbers. In Java, there are various approaches to calculating the LCM of two or more numbers, including using loops, recursion, and built-in libraries such as the java.util package. By understanding and implementing these techniques, you can efficiently find the LCM of any given set of numbers in your Java programs.

FAQs (Frequently Asked Questions) related to LCM of Two Numbers in Java

Q1. What is the LCM of two numbers?
Ans. The LCM of two numbers is the smallest positive integer that is divisible by both numbers without leaving a remainder.

Q2. How can I calculate the LCM of two numbers in Java?
Ans. There are several approaches to calculating the LCM of two numbers in Java. One common method involves finding the greatest common divisor (GCD) of the two numbers and then using it to calculate the LCM using the formula LCM = (num1 * num2) / GCD(num1, num2).

Q3. Can I find the LCM of more than two numbers?
Ans. Yes, you can find the LCM of multiple numbers in Java. One approach is to find the LCM of two numbers first, and then iteratively find the LCM of the previous result and the next number until you have processed all the numbers.

Q4. Are there any built-in functions or libraries in Java to calculate the LCM?
Ans. Yes, Java provides the java.util package, which includes the BigInteger class that has a built-in method gcd() to calculate the greatest common divisor (GCD). You can utilize this method along with the formula mentioned earlier to calculate the LCM.

Q5. Can I use recursion to calculate the LCM in Java?
Ans. Yes, recursion can be used to calculate the LCM in Java. By recursively finding the LCM of two numbers, you can extend the process to find the LCM of multiple numbers as well.

Q6. Are there any special cases to consider when calculating the LCM in Java?
Ans. Yes, when dealing with zero or negative numbers, you should handle them appropriately. For example, if one of the numbers is zero, the LCM would be zero. If any of the numbers are negative, you can convert them to positive before calculating the LCM, as the LCM is always positive.