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).

LCM

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

Get Prime

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);
    }
    }


  • 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));
    }
    }


  • 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);
    }
    }


  • 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);
    }


  • 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();

    }
    }


  • 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();
    }
    }


  • 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);

    }
    }


  • 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;
    }
    }
    }


  • 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);
    }
    }