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

In this article we 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. These two numbers are divided and remainder will become divisor and previous divisor become dividend.

Repeat above process until remainder is zero. By doing this we get GCD as divisor. Similarly here’s the java program to find lcm of 2 numbers.

Now let’s see how to find gcd and lcm of two numbers in java using euclidean algorithm,

import java.util.Scanner;

public class GCDLCMEuclid
{
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter two numbers : ");
      int num1 = sc.nextInt();
      int num2 = sc.nextInt();     
      System.out.println("GCD of two numbers : " + calculateGCD(num1, num2));
      System.out.println("LCM of two numbers : " + calculateLCM(num1, num2));
      sc.close();
   }

   static int calculateGCD(int a, int b)
   {
      int c = 0, p, q;
      p = (a > b) ? a : b;
      q = (a < b) ? a : b;
      c = q;
      while(p % q != 0)     
      {
         c = p % q;
         p = q;
         q = c;
      }
      return c;
   }

   static int calculateLCM(int a, int b)
   {
      int c;
      c = (a > b) ? a : b;
      while(true)
      {
         if(c % a == 0 && c % b == 0)
         {
            return c;
         }
         ++c;
      }   
   }
}

Output:

Enter two numbers :
8
59
GCD of two numbers : 1
LCM of two numbers : 472