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 stored in two long variables a and b.

These two variables are then passed as parameters to method findGCD(). Now in this method 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. 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

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

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