1. Home

Step by Step Java Tutorial Concepts - From Beginner to Pro

Learn Java programming from basics to advanced concepts with our comprehensive tutorials. Start from scratch and elevate your skills to expert level.

• 192 Lessons
• 32 Hours
184.Â

# LCM of Two Numbers in Java

Updated on 12/09/20245,309 Views

## Introduction

The LCM of two integers is the smallest positive integer divided by both numbers without leaving a remainder. In Java, various methods exist for computing the LCM of two integers. A straightforward method is to find all prime factors of both numbers and the union of all factors present in both numbers. Finally, return the product of the union's items. Another method is based on the LCM formula for two numbers 'a' and 'b': a x b = LCM(a, b) x GCD(a, b), where GCD stands for Greatest Common Divisor.

You can use loops, recursion, or built-in tools such as the java.util package to compute the LCM of two numbers in Java. Obtaining the GCD of the two numbers and then using it to compute the LCM using the formula LCM = (n1 * n2) / GCD is one of the common approaches.

Another method is to use loops to check if the LCM is divisible by both numbers. If it is, one shows the LCM and breaks the loop. If this is not the case, one increases the LCM variable and re-tests the divisibility criteria.

## Overview

This Java tutorial will examine several approaches to finding the LCM of two integers while providing sample code samples. We will discuss algorithmic techniques and built-in Java features that can make locating the LCM easier.

You will have a solid basis for resolving multiples and divisibility issues by learning to find the LCM of two numbers in Java using the function java.math or java.util. Let's get started with the strategies for obtaining the LCM in Java programming!

## Properties of LCM

LCM is associative, commutative, and distributive, which means:

• Associative: LCM(p, q) = LCM(q, p)
• Commutative: LCM(p, q) = LCM(q, p)
• Distributive: LCM(p, LCM(q, r)) = LCM(LCM(p, q), LCM(p, r))

There are 4 methods to find the LCM:

• Using the GCD Method.
• Using the Prime Factorisation Method.
• Using the Division Method.

LCM can be calculated using the built-in gcd() function in the java.math package. Also, one can calculate the LCM of two numbers in Java using recursion.

These are some of the significant aspects of LCM in Java that are extensively employed in solving real-world situations.

## How to Find LCM?

To find the LCM of two numbers, we first break down each number into its prime factors. Prime factorization is expressing a number as a product of prime numbers.

For instance, the prime factorization of 12 is 2^2 * 3, and the prime factorization of 15 is 3 * 5.

We must first determine the highest power of each prime factor that appears in any of the numbers. Then, we take the maximum exponent for each prime factor. Finally, we multiply all the prime factors using the highest powers obtained in the previous step.

The final product will give us the LCM of the given numbers.

Here is an example:

Question: Find the LCM of 12 and 15.

First, the prime factorization:

The prime factorization of 12 is 2^2 * 3.

The prime factorization of 15 is 3 * 5.

Then, we determine the highest power:

The highest power of 2 is 2^2.

The highest power of 3 is 3.

The highest power of 5 is 5.

Finally, we multiply the prime factors:

LCM = 2^2 * 3 * 5 = 60.

Therefore, the LCM of 12 and 15 is 60.

Let us now discuss the different methods available to us for finding out the LCM of two numbers in Java.

### Using the Greatest Common Divisor (GCD) Method

`public class upGradLCMCalculator {Â  Â Â Â  Â  // Function to calculate the GCD (Greatest Common Divisor) of two numbersÂ  Â  public static int gcd(int a, int b) {Â  Â  Â  Â  if (b == 0) {Â  Â  Â  Â  Â  Â  return a;Â  Â  Â  Â  }Â  Â  Â  Â  return gcd(b, a % b);Â  Â  }Â  Â Â Â  Â  // Function to calculate the LCM using the GCD methodÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  int gcdResult = gcd(a, b);Â  Â  Â  Â  int lcmResult = (a * b) / gcdResult;Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In the gcd() function, we calculate the GCD (Greatest Common Divisor) of two numbers (a and b) using the Euclidean algorithm. The function is implemented recursively by repeatedly taking the remainder of dividing a by b until b becomes 0. At that point, the GCD is found, and we return the value of a.

In the lcm() function, we call the gcd() function to obtain the GCD of a and b. Then, we calculate the LCM using the formula: LCM = (a * b) / GCD(a, b). We store the result in lcmResult and return it.

In the main() function, we call the lcm() function with two numbers (num1 and num2) and store the result in lcmResult. Finally, we print the LCM to the console.

### Using Multiples of Numbers

`public class upgradLCMCalculator {Â  Â Â Â  Â  // Function to calculate the LCM using multiples of numbersÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  int lcmResult = Math.max(a, b);Â  Â  Â  Â Â Â  Â  Â  Â  while (true) {Â  Â  Â  Â  Â  Â  if (lcmResult % a == 0 && lcmResult % b == 0) {Â  Â  Â  Â  Â  Â  Â  Â  break;Â  Â  Â  Â  Â  Â  }Â  Â  Â  Â  Â  Â  lcmResult += Math.max(a, b);Â  Â  Â  Â  }Â  Â  Â  Â Â Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In this program, in the lcm() function, we start by initializing the lcmResult variable with the maximum of the two input numbers (Math.max(a, b)). We then enter a while loop until we find a number (lcmResult) divisible by both a and b.

Inside the while loop, we use the condition lcmResult % a == 0 && lcmResult % b == 0 to check if lcmResult is a multiple of both a and b. If it is, we break out of the loop. Otherwise, we increment lcmResult by the larger of the two numbers (Math.max(a, b)).

Once the loop terminates, we have found the LCM, and we return the value of lcmResult.

In the main() function, we call the lcm() function with two numbers (num1 and num2) and store the result in lcmResult. Finally, we print the LCM to the console.

### LCM Using Prime Factorization Method

`public class LCMCalculator {Â  Â Â Â  Â  // Function to calculate the LCM using the prime factorization methodÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  // Calculate the prime factorization of aÂ  Â  Â  Â  int[] factorsA = primeFactorization(a);Â  Â  Â  Â Â Â  Â  Â  Â  // Calculate the prime factorization of bÂ  Â  Â  Â  int[] factorsB = primeFactorization(b);Â  Â  Â  Â Â Â  Â  Â  Â  // Merge the prime factors from both numbers and multiply themÂ  Â  Â  Â  int[] mergedFactors = mergeFactors(factorsA, factorsB);Â  Â  Â  Â  int lcmResult = multiplyFactors(mergedFactors);Â  Â  Â  Â Â Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â Â Â  Â  // Function to calculate the prime factorization of a numberÂ  Â  public static int[] primeFactorization(int num) {Â  Â  Â  Â  // Implement your prime factorization logic hereÂ  Â  Â  Â  // Return an array of prime factorsÂ  Â  }Â  Â Â Â  Â  // Function to merge the prime factors from two numbersÂ  Â  public static int[] mergeFactors(int[] factorsA, int[] factorsB) {Â  Â  Â  Â  // Implement your logic to merge the prime factorsÂ  Â  Â  Â  // Return an array of merged prime factorsÂ  Â  }Â  Â Â Â  Â  // Function to multiply the prime factorsÂ  Â  public static int multiplyFactors(int[] factors) {Â  Â  Â  Â  // Implement your logic to multiply the prime factorsÂ  Â  Â  Â  // Return the result of multiplying the factorsÂ  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In the lcm() function, we start by calculating the prime factorization of both input numbers (a and b) using the primeFactorization() function. This function should implement the logic to find the prime factors of a given number and return them as an array.

Next, we merge the prime factors obtained from both numbers using the mergeFactors() function. This function should merge the arrays of prime factors, considering the highest power for each prime factor. The merged factors are stored in the mergedFactors array.

Finally, we calculate the LCM by multiplying the merged prime factors using the multiplyFactors() function. This function should implement the logic to multiply the factors and return the result.

In the main() function, we call the lcm() function with two numbers (num1 and num2) and store the result in lcmResult. Finally, we print the LCM to the console.

To complete the implementation, you need to provide the actual logic for the primeFactorization(), mergeFactors(), and multiplyFactors() functions according to your desired prime factorization and multiplication algorithms.

### LCM Using While loop and if Statement

`public class upGradLCMCalculator {Â  Â Â Â  Â  // Function to calculate the LCM using a while loop and if statementÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  int lcmResult = Math.max(a, b);Â  Â  Â  Â Â Â  Â  Â  Â  while (true) {Â  Â  Â  Â  Â  Â  if (lcmResult % a == 0 && lcmResult % b == 0) {Â  Â  Â  Â  Â  Â  Â  Â  break;Â  Â  Â  Â  Â  Â  }Â  Â  Â  Â  Â  Â  lcmResult++;Â  Â  Â  Â  }Â  Â  Â  Â Â Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In the lcm() function, we start by initializing the lcmResult variable with the maximum of the two input numbers (Math.max(a, b)). We then enter a while loop until we find a number (lcmResult) divisible by both a and b.

Inside the while loop, we use the condition lcmResult % a == 0 && lcmResult % b == 0 to check if lcmResult is a multiple of both a and b. We break out of the loop if the condition is true, indicating that lcmResult is divisible by both numbers. Otherwise, we increment lcmResult by 1 (lcmResult++) and continue the loop.

Once the loop terminates, we have found the LCM and get the value of lcmResult.

### LCM Using Multiples of Numbers

`public class upGradLCMCalculator {Â  Â Â Â  Â  // Function to calculate the LCM using multiples of numbersÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  int lcmResult = Math.max(a, b);Â  Â  Â  Â Â Â  Â  Â  Â  while (true) {Â  Â  Â  Â  Â  Â  if (lcmResult % a == 0 && lcmResult % b == 0) {Â  Â  Â  Â  Â  Â  Â  Â  break;Â  Â  Â  Â  Â  Â  }Â  Â  Â  Â  Â  Â  lcmResult += Math.max(a, b);Â  Â  Â  Â  }Â  Â  Â  Â Â Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In the lcm() function, we start by initializing the lcmResult variable with the maximum of the two input numbers (Math.max(a, b)). We then enter a while loop until we find a number (lcmResult) divisible by both a and b.

Inside the while loop, we use the condition lcmResult % a == 0 && lcmResult % b == 0 to check if lcmResult is a multiple of both a and b. We break out of the loop if the condition is true, indicating that lcmResult is divisible by both numbers. Otherwise, we increment lcmResult by the larger of the two numbers (Math.max(a, b)) to consider the next multiple.

Once the loop terminates, we find the LCM and get the value of lcmResult.

### Another Method to Calculate LCM using GCD

`public class upGradLCMCalculator {Â  Â  // Function to calculate the GCD of two numbers using the Euclidean algorithmÂ  Â  public static int gcd(int a, int b) {Â  Â  Â  Â  if (b == 0) {Â  Â  Â  Â  Â  Â  return a;Â  Â  Â  Â  }Â  Â  Â  Â  return gcd(b, a % b);Â  Â  }Â  Â  // Function to calculate the LCM of two numbers using the GCD methodÂ  Â  public static int lcm(int a, int b) {Â  Â  Â  Â  // Calculate the absolute values of a and b to handle negative numbersÂ  Â  Â  Â  int absA = Math.abs(a);Â  Â  Â  Â  int absB = Math.abs(b);Â  Â  Â  Â Â Â  Â  Â  Â  // Calculate the GCDÂ  Â  Â  Â  int gcdResult = gcd(absA, absB);Â  Â  Â  Â Â Â  Â  Â  Â  // Calculate the LCM using the formula: LCM = (absA * absB) / GCDÂ  Â  Â  Â  int lcmResult = (absA * absB) / gcdResult;Â  Â  Â  Â Â Â  Â  Â  Â  return lcmResult;Â  Â  }Â  Â  public static void main(String[] args) {Â  Â  Â  Â  int num1 = 12;Â  Â  Â  Â  int num2 = 15;Â  Â  Â  Â  int lcmResult = lcm(num1, num2);Â  Â  Â  Â Â Â  Â  Â  Â  System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcmResult);Â  Â  }}`

In this example, we have two functions: gcd() to calculate the GCD using the Euclidean algorithm and lcm() to calculate the LCM using the GCD method. The main() function demonstrates how to use the lcm() function to find the LCM of two numbers (12 and 15 in this case). The result is then printed to the console.

## Conclusion

The LCM, a fundamental mathematical concept, can be used to identify the lowest multiple divided by two or more integers. In Java, there are many ways to calculate the LCM of two or more numbers, including looping, recursion, and built-in utilities like java.util package. By researching and employing these strategies, one can obtain the LCM of any given collection of integers in Java applications.

## FAQs

1. How to find the LCM of two numbers in Java without using GCD?

One technique to discover the LCM of two integers in Java without using GCD is starting with the largest of the two numbers and incrementing the bigger number until it becomes divisible by the smaller number.

1. How to find the LCM of two numbers in Java using for loop?

To get the LCM of two integers in Java using a for loop, first, compute their GCD using Euclid's approach and then apply the LCM = (n1 * n2) / GCD formula.

1. How to find the LCM of two numbers in Java using a scanner?

To obtain the LCM of two numbers in Java, you can use the scanner class to read the two values from the user.

1. How to find the GCD and LCM of two numbers in Java?

You can apply Euclid's method to find the GCD and LCM of two numbers in Java. Then, using the equation LCM = (n1 * n2) / GCD, you get the LCM of the two integers.

1. How to find the LCM of two numbers in Java using prime factorization?

To compute the LCM of two integers in Java using prime factorization, identify the prime factors of both numbers. Then multiply the LCM of the two numbers by the largest power of each prime component.

Director of Engineering

Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working â€¦Read More

###### Need More Help? Talk to an Expert
+91
*
By clicking, I accept theT&Cand
Join 10M+ Learners & Transform Your Career
Learn on a personalised AI-powered platform that offers best-in-class content, live sessions & mentorship from leading industry experts.

Talk to our experts. Weâ€™re available 24/7.

Indian Nationals

1800 210 2020

Foreign Nationals

+918045604032

## Disclaimer

upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...