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.

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

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[0], arrNumbers[1]);
      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);
      System.out.println("Please enter first number: ");
      int number1 = sc.nextInt();
      System.out.println("Please enter second number: ");
      int number2 = sc.nextInt();
      System.out.println("Please enter third number: ");
      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:

Please enter first number: 12
Please enter second number: 48
Please enter third number: 84
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