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 scanner class. These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Also read – polymorphism in java

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

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 calculate 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 calculate LCM : ");
      long c = sc.nextLong();
      long d = sc.nextLong();
      obj.findLCM(c, d);
      sc.close();
   }
}

Output:

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

GCD of two numbers in java using recursion

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

public class GCDUsingRecursion
{
   public static void main(String[] args) 
   {
      int number1 = 898, number2 = 90;
      int gcd = gcdRecursion(number1, number2);
      System.out.printf("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.print("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

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

import java.util.Scanner;

public class GCDOfThreeNumbers 
{
   public static void main(String[] args) 
   {
      Scanner sc = new Scanner(System.in);
      System.out.print("Please enter first number: ");
      int number1 = sc.nextInt();
      System.out.print("Please enter second number: ");
      int number2 = sc.nextInt();
      System.out.print("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