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

### 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 (1st 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 (1st 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: