LCM of two numbers using Java

April 11, 2023

LCM of Two Numbers

Here, in this page we will discuss the LCM of two numbers using java. LCM is a Least Common Multiple, means LCM of two numbers is the number which is the smallest common multiple of both numbers. It is also referred to as the Lowest Common Multiple(LCM) or Least Common Denominator(LCD).

We will learn

Method 1: A linear way to calculate LCM
Method 2: Modified interval Linear way
Method 3: Simple usage of HCF calculation to determine LCM
Method 4: Repeated subtraction to calculate HCF and determine LCM
Method 5: Recursive repeated subtraction to calculate HCF and determine LCM
Method 6: Modulo Recursive repeated subtraction to calculate HCF and determine LCM

Method 1

Algorithm

For a input num1 and num2. This method uses two following observations –

LCM of two numbers will at least be equal or greater than max(num1, num2)
Largest possibility of LCM will be num1 * num2

When iterating in (i) We can linearly find an (i) that is divisible by both num1 & num2

Method 1 : C++ Code

Run

public class Main
{
  public static void main (String[]args)
  {
    int num1 = 36, num2 = 60, lcm = 0;

    // finding the larger number here
    int max = (num1 > num2) ? num1 : num2;

    // LCM will atleast be >= max(num1, num2)
    // Largest possibility of LCM will be num1*num2
    for (int i = max; i <= num1 * num2; i++)
      {
     if (i % num1 == 0 && i % num2 == 0)
        {
         lcm = i;
         break;
        }
      }
    System.out.println ("The LCM: " + lcm);
  }
}

Output

LCM of 12 and 14 is 84

Method 2

Algorithm

For input num1 and num2. This method uses two following observations –

Rather than linearly checking for LCM by doing i++. We can do i = i + max
Starting with i = max (num1, num2)
The next possibility of LCM will be ‘max’ interval apart

Method 3

Algorithm

Initialize HCF = 1
Run a loop in the iteration of (i) between [1, min(num1, num2)]
Note down the highest number that divides both num1 & num2
If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i
Use lcm formula :- (num1*num2) / hcf
Print the output

Method 3 : C++ Code

Run

public class Main
{
  public static void main (String[]args)
  {
    int num1 = 16, num2 = 24, hcf = 1;

    // calculating HCF here
    for (int i = 1; i <= num1 || i <= num2; i++)
      {
     if (num1 % i == 0 && num2 % i == 0)
        hcf = i;
      }

    // LCM formula
    int lcm = (num1 * num2) / hcf;
    System.out.println ("The LCM: " + lcm);
  }
}

Output

LCM of 12 and 14 is 84

Method 4

Algorithm

Run a while loop until num1 is not equals to num2
If num1>num2 then num1 = num1 – num2
Else num2 = num2 – num1
After the loop ends both num1 & num2 stores HCF
Use LCM formula :- (num1*num2) / hcf
Print Output

Method 4 : C++ Code

Run

public class Main
{
  public static void main (String[]args)
  {
    int num1 = 144, num2 = 32;

    int hcf = getHCF (num1, num2);
      System.out.println ("The HCF: " + hcf);

    // LCM formula
    int lcm = (num1 * num2) / hcf;
      System.out.println ("The LCM: " + lcm);
  }

  static int getHCF (int num1, int num2)
  {

    // using repeated subtraction here
    while (num1 != num2)
      {
     if (num1 > num2)
        num1 -= num2;
     else
        num2 -= num1;
      }

    return num1;
  }
}

Output

LCM of 12 and 14 is 84

Method 5

Algorithm

Checked whether any of the input is 0 then return sum of both numbers
If both input are equal return any of the two numbers
If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
Else Recursively call findHCF(num1, num2-num1)

Method 5 : C++ Code

Run

public class Main
{
  public static void main (String[]args)
  {
    int num1 = 144, num2 = 32;

    int hcf = getHCF (num1, num2);
      System.out.println ("The HCF: " + hcf);

    // LCM formula
    int lcm = (num1 * num2) / hcf;
      System.out.println ("The LCM: " + lcm);



  }

  // Recursive function for repeated subtraction HCF calculation
  static int getHCF (int num1, int num2)
  {
    // Handles the case when one of the number is 0 (num1) 
    // Check alert above in explanation
    if (num1 == 0)
      return num2;

    // Handles the case when one of the number is 0 (num2)
    // Check alert above in explanation
    if (num2 == 0)
      return num1;

    // base case
    if (num1 == num2)
      return num1;

    // num1 is greater
    if (num1 > num2)
      return getHCF (num1 - num2, num2);

    return getHCF (num1, num2 - num1);
  }
}

Output

LCM of 12 and 14 is 84

Method 6

Algorithm

This method uses recursion.

In Addition, we are using modulo operation to reduce the number of subtractions required and improve the time complexity

For this method, you need to know how to calculate HCF, check this post here

We use repeated Modulo Recursive subtraction (Euclidean Algorithm) to calculate the HCF.

Method 6 : C++ Code

Run

public class Main
{
  public static void main (String[]args)
  {
    int num1 = 144, num2 = 32;

    int hcf = getHCF (num1, num2);
      System.out.println ("The HCF: " + hcf);

    // LCM formula
    int lcm = (num1 * num2) / hcf;
      System.out.println ("The LCM: " + lcm);
  }

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
  static int getHCF (int a, int b)
  {
    return b == 0 ? a : getHCF (b, a % b);
  }
}

Output

LCM of 12 and 14 is 84

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

9 comments on “LCM of two numbers using Java”

Ravi Kant
public class Lcm5 {
public static void main(String[] args) {
int n1,n2,temp1,temp2;
Scanner scanner=new Scanner(System.in);
System.out.println(“print first no”);
n1=scanner.nextInt();
System.out.println(“print second no”);
n2=scanner.nextInt();
temp1=n1;
temp2=n2;
while (n1%n2!=0){
int remainder=(n1%n2);
n1=n2;
n2=remainder;
}
int gcd=n2;
int lcm=temp1*temp2/gcd;
System.out.println(“gcd:”+gcd);
System.out.println(“lcm”+lcm);
}
}

Log in to Reply
Kundan
import java.util.*;
class main{
static String LCM(int num1,int num2){
// method 1
int a = num1,b=num2;
int i=2;
int min = Math.min(num1,num2);
int res = 1;
while(i1;i–){
// if(num1%i==0 && num2%i==0){
// num1 /=i;
// num2 /=i;
// res *=i;
// if(num1==1 || num2==1){
// break;
// }
// }
// }
// res *= num1*num2;
// return “LCM of “+a +” and “+b +” is : “+res;
}
public static void main(String[] args) {
int num1 = 36,num2 = 60;
System.out.println(LCM(num1,num2));
}
}

Log in to Reply
Dhivya
octal to binary conversion

import java.util.HashMap;
import java.util.Scanner;

public class binary_Octal {
public static void main(String[] args) {
HashMap bi =new HashMap();
bi.put(000,0);
bi.put(001,1);
bi.put(010,2);
bi.put(011,3);
bi.put(100,4);
bi.put(101,5);
bi.put(110,6);
bi.put(111,7);

Scanner s= new Scanner(System.in);
String result =” “;
long num = s.nextLong();
long n=num;
while(n !=0){
long rem=0;
rem=n%1000;
if(n!=0) {
result = Integer.toString(bi.get((int) rem)) + result;

}
n=n/1000;

}
System.out.println(result);
}
}

Log in to Reply
Divya
public static void HighestCommonFector_2(int n1, int n2){
int m1 = n1, m2 = n2;
int rem = 0;
while(n2 % n1 != 0){
rem = n2 % n1;
n1 = n2;
n2 = rem;
}
int hcg = rem;
int lcm = m1 * m2 / hcg;

System.out.println(” LCM of ” + m1 + ” and ” + m2 + ” is : ” + lcm);
}

Log in to Reply
Ujjwal
import java.util.Scanner;

public class LCM {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(“Enter first number “);
int a = sc.nextInt();
System.out.println(“Enter second number “);
int b= sc.nextInt();
int hcf=1;

for(int i=1; i<=a || i<=b ; i++) {
if( a%i ==0 && b%i==0) {
hcf=i;
}
}
System.out.println(hcf);
int lcm= (a*b)/hcf;
System.out.println(lcm);
sc.close();

}
}

Log in to Reply
Yatin
import java.util.*;
public class Lcm {

public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
System.out.print(“Enter the first no:”);
int num1=sc.nextInt();
System.out.print(“Enter the second no:”);
int num2=sc.nextInt();
int a=num1>num2?num1:num2;
int b=num1<num2?num1:num2;
for(int i=1;i<=b;i++) {
int rem=a*i;
if(rem%b==0) {
System.out.println(rem);
break;
}
}
sc.close();
}
}

Log in to Reply
soumyaranjan
import java.util.*;
public class LCM_Two_Numbers {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(“Enter first number:”);
int firstNumber = sc.nextInt();
System.out.println(“Enter second number:”);
int secondNumber = sc.nextInt();
findLCM(firstNumber,secondNumber);
sc.close();

}
public static void findLCM(int number_1,int number_2)
{
int i;
for (i = 1; i <= number_1 *number_2; i++) {
if (i % number_1 == 0 && i % number_2 == 0) {
break;
}
}
System.out.println("LCM of " + number_1 + " and " + number_2 + " is " + i);

}
}

Log in to Reply
Rakesh gowda
public class Lcm {
public static void main(String[] args) {
Scanner scan =new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
int h = a>b?a:b;
for(int i = a*b;i>=h;i=i-h)
{
if(i%a==0 && i%b==0)
{
System.out.println(i);
break;
}
}
}

Log in to Reply
Aditi
import java.util.*;
class LCM{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int num1=sc.nextInt();
int num2=sc.nextInt();
int gcd=1;
if(num1!=num2)
{
for(int i=1;i<=num1&&i<=num2;i++)
{
if(num1%i==0&&num2%i==0) gcd=i;
}
}
else System.out.println("enter different nuimbers");
System.out.println(gcd);
int lcm=(num1/gcd)*num2;
System.out.println("LCM= "+lcm);
}
}

Log in to Reply

Unlock this article for Free,
by logging in

LCM of two numbers using Java