Euclid's algorithm java - Java Program to Find LCM of Two Numbers Using Euclid’s Algorithm

Euclid’s algorithm java: In the previous article, we have seen Java Program to Compute GCD

In this article we are going to see how to find the LCM using Java programming language.

Java Program to Find LCM of Two Numbers Using Euclid’s Algorithm

In this program we will will use Euclid’s approach to find LCM.

LCM = (1st number * (2nd number/GCD))

Example:

Let a and b are two numbers.

a = 20

b = 30

Common factors of (20,30) = 1, 2, 5, 10

So, GCD = 10

Now, LCM = (1st number * (2nd number/GCD))

=>LCM = (20*(10/10))

=>LCM = 20*1= 20

Let’s see different ways to find the LCM by using Euclid’s algorithm.

By Using Static Input Value
By Using User Input Value

Method-1: Java Program to Find LCM of Two Numbers Using Euclid’s Algorithm By Using Static Input Value

Approach:

Declare an integer variable say ‘a’ and assign the value, it is the value of the first number.
Declare an integer variable say ‘b’ and assign the value, it is the value of the second number.
Declare an integer variable say ‘GCD’ and initialize it to 1. Then find GCD.
Then find LCM as (1^st number * (2nd number/GCD)).
Print the result.

Program:

import java.io.*;
public class Main
{
    public static void main(String [] args)
    {
        //two numbers declared with value
        int a = 20;
        int b = 10;    
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of a
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
            if(a%i == 0 && b%i==0)
                GCD = i;
        }
        
        //find LCM using formula
        int LCM = (a * (b / GCD));
        //printing the result
        System.out.println("The LCM of ("+ a + "," + b + ") is " + LCM);
    }
}

Output:

The LCM of (20,10) is 20

Method-2: Java Program to Find LCM of Two Numbers Using Euclid’s Algorithm By Using User Input Value

Approach:

Declare an integer variable say ‘a’ and take the value as user input, it is the value of the first number.
Declare an integer variable say ‘b’ and take the value as user input, it is the value of the second number.
Declare an integer variable say ‘GCD’ and initialize it to 1. Then find GCD.
Then find LCM as (1^st number * (2nd number/GCD)).
Print the result.

Program:

import java.util.*;
public class Main
{
    public static void main(String [] args)
    {
        //Scanner class object created
        Scanner s = new Scanner(System.in); 
        //Taking user input of two numbers
        System.out.println("Enter the value of 1st number:");
        int a = s.nextInt();                                           
        System.out.println("Enter the value of 2nd number:");
        int b = s.nextInt();     
   
        //integer variable GCD declared to hold GCD value
        //also initualized to 1
        int GCD =  1; 
        
        //checking the smaller number between a and b
        //and assigning the smaller number to variable n
        int n=0;
        if(a<b)
            n=a;
        else
            n=b;
    
        //Here i is the factor of a
        //since the 1st factor of any number is 1. Hence we have initialized it to 1.
        //loop will go upto 'n' which holds the smaller number between 'a' and 'b'
        for(int i = 1; i<=n; i++) 
        {
            //Checking largest integer that divides both a and b with no remainder
            if(a%i == 0 && b%i==0)
                GCD = i;
        }
        
        //find LCM using formula
        int LCM = (a * (b / GCD));
        //printing the result
        System.out.println("The LCM of ("+ a + "," + b + ") is " + LCM);
    }
}

Output:

Enter the value of 1st number:
20
Enter the value of 2nd number:
10
The LCM of (20,10) is 20

Have you mastered basic programming topics of java and looking forward to mastering advanced topics in a java programming language? Go with these ultimate Advanced java programs examples with output & achieve your goal in improving java coding skills.

Related Java Programs: