# Java program find GCD and LCM of two numbers using euclid’s algorithm

Let’s learn java program find GCD and LCM of two numbers using euclid’s algorithm.

## Java program find GCD and LCM of two numbers using euclid’s algorithm

In the below java program user enters two numbers using nextLong() method of Scanner class.

These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Repeat above steps until remainder is zero. By doing this we get GCD as divisor.

Also read – java program to find lcm of two numbers

Now let’s see java program to find gcd and lcm using euclid’s algorithm.

```import java.util.Scanner;
public class GCDLCMEuclid
{
// gcd java
void findGCD(long num1, long num2)
{
while(num2 > 0)
{
long temp = num2;
num2 = num1 % num2;
num1 = temp;
}
System.out.println("GCD is : " + num1);
}
// lcm java
void findLCM(long num1, long num2)
{
long a = num1;
long b = num2;
while(num2 > 0)
{
long temp = num2;
num2 = num1 % num2;
num1 = temp;
}
long gcd = num1;
long lcm = (a * (b / gcd));
System.out.println("LCM is : " + lcm);
}
public static void main(String[] args)
{
GCDLCMEuclid obj = new GCDLCMEuclid();
System.out.println("Please enter any two numbers to find GCD : ");
Scanner sc = new Scanner(System.in);
long a = sc.nextLong();
long b = sc.nextLong();
obj.findGCD(a, b);
System.out.println("Please enter any two numbers to find LCM : ");
long c = sc.nextLong();
long d = sc.nextLong();
obj.findLCM(c, d);
sc.close();
}
}

```

Output:

Please enter any two numbers to find GCD :
4
11
GCD is : 1
Please enter any two numbers to find LCM :
23
56
LCM is : 1288

GCD of two numbers in java using recursion

Let’s find gcd of two numbers in java using recursion.

```public class GCDUsingRecursion
{
public static void main(String[] args)
{
int number1 = 898, number2 = 90;
int gcd = gcdRecursion(number1, number2);
System.out.println("G.C.D of " + number1 + " and " + number2 + " is " + gcd);
}
public static int gcdRecursion(int num1, int num2)
{
if(num2 != 0)
{
return gcdRecursion(num2, num1 % num2);
}
else
{
return num1;
}
}
}

```

Output:

G.C.D of 898 and 90 is 2

extended euclidean algorithm java

```public class ExtendedEuclideanAlgorithm
{
public static void main(String[] args)
{
int a = 1, b = 1;
int number1 = 84, number2 = 24;
int gcd = extendedEuclidean(number1, number2, a, b);
System.out.println("GCD of extended euclidean algorithm java (" + number1 + ", " + number2 + ") = " + gcd);
}
public static int extendedEuclidean(int x, int y, int num1, int num2)
{
if(x == 0)
{
num1 = 0;
num2 = 1;
return y;
}
int p = 1, r = 1;
int gcd = extendedEuclidean(y % x, x, p, r);
// results of recursive call
num1 = r - (y / x) * p;
num2 = p;
return gcd;
}
}

```

Output:

GCD of extended euclidean algorithm java (84, 24) = 12

gcd of n numbers in java

Let’s learn gcd of n numbers in java.

```public class GCDOfNNumbers
{
public static void main(String[] args)
{
int[] arrNumbers = {25, 46, 61, 88};
int output = gcdNumbers(arrNumbers, arrNumbers);
for(int a = 2; a < arrNumbers.length; a++)
{
output = gcdNumbers(output, arrNumbers[a]);
}
System.out.println("gcd of n numbers in java: " + output);
}
public static int gcdNumbers(int x, int y)
{
int result = 0;
while(y > 0)
{
int temp = y;
y = x % y;
x = temp;
result = x;
}
return result;
}
}

```

Output:

gcd of n numbers in java: 1

gcd of three numbers in java

Here’s gcd of three numbers in java.

```import java.util.Scanner;
public class GCDOfThreeNumbers
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int number1 = sc.nextInt();
int number2 = sc.nextInt();
int number3 = sc.nextInt();
int gcdNumbers = GCDOfThreeNumbers.findGCD(number1, number2, number3);
System.out.println("GCD of three numbers " + number1 + ", " + number2 + " and " + number3 + " is: " + gcdNumbers);
sc.close();
}
public static int findGCD(int x, int y)
{
if(y == 0)
{
return x;
}
else
{
return findGCD(y, x % y);
}
}
public static int findGCD(int x, int y, int z)
{
return findGCD(findGCD(x, y), z);
}
}

```

Output:

GCD of three numbers 12, 48 and 84 is: 12

gcd of two numbers in java

GCD of two numbers is the largest positive number that divides both numbers without remainder.

For example:

10 – 1, 2, 5

15 – 1, 3, 5

GCD of 10 and 15 is 5.

Click here to learn program on gcd of two numbers in java.

lcm and gcd of two numbers in java

Here’s the program on lcm and gcd of two numbers in java.

```import java.util.Scanner;
public class LCMAndGCD
{
static int findGcd(int num1, int num2)
{
int rem = 0, a, b;
a = (num1 > num2) ? num1 : num2;
b = (num1 < num2) ? num1 : num2;
rem = b;
while(a % b != 0)
{
rem = a % b;
a = b;
b = rem;
}
return rem;
}
static int findLcm(int num1, int num2)
{
int a;
a = (num1 > num2) ? num1 : num2;
while(true)
{
if(a % num1 == 0 && a % num2 == 0)
return a;
++a;
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Please enter two numbers to find lcm and gcd: ");
int p = sc.nextInt();
int q = sc.nextInt();
System.out.println("GCD of two numbers is: " + findGcd(p, q));
System.out.println("LCM of two numbers is: " + findLcm(p, q));
sc.close();
}
}

```

Output:

Please enter two numbers to find lcm and gcd:
48
36
GCD of two numbers is: 12
LCM of two numbers is: 144

Also read – lcm of two numbers in java