GCD of two numbers in java

Let’s learn GCD of two numbers in java.

GCD of two numbers in java

GCD (Greatest Common Divisor) of two numbers is the largest positive number that divides both numbers without remainder.

For example: GCD of 12 and 16 is 4

To find GCD of two numbers an efficient solution is to use Euclidean algorithm. Let’s see java program on GCD of two numbers.

public class GCDUsingEuclideanAlgorithm
{
   static int gcdRecursion(int num1, int num2)
   {
      // each number divides 0
      if(num1 == 0)
         return num2;
      if(num2 == 0)
         return num1;
      if(num1 == num2)
         return num1;
      // num1 is greater
      if(num1 > num2)
         return gcdRecursion(num1 - num2, num2);
      return gcdRecursion(num1, num2 - num1);
   }
   public static void main(String[] args)
   {
      int num1 = 90, num2 = 57;
      System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcdRecursion(num1, num2));
   }
}

Output:

GCD of 90 and 57 is 3

Similarly a more efficient solution would be using modulo operator in Euclidean algorithm.

public class GCDUsingEuclideanAlgorithm
{
   static int gcdRecursion(int num1, int num2)
   {
      if(num2 == 0)
         return num1;
      return gcdRecursion(num2, num1 % num2);
   }
   public static void main(String[] args)
   {
      int num1 = 117, num2 = 67;
      System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcdRecursion(num1, num2));
   }
}

Output:

GCD of 117 and 67 is 1

Now let’s see gcd of two numbers in java program using while loop and if else.

import java.util.Scanner;
public class GCDOfTwoNumbers 
{
   public static void main(String[] args) 
   {
      int a, b;
      Scanner sc = new Scanner(System.in);
      System.out.print("Please enter first number: ");
      a = sc.nextInt();
      System.out.print("Please enter second number: ");
      b = sc.nextInt();
      while(a != b) 
      {
         if(a > b)
         {
            a = a - b;
         }
         else
         {
            b = b - a;
         }
      }
      System.out.println("GCD of two numbers is: " + a);
      sc.close();
   }
}

Output:

Please enter first number: 90
Please enter second number: 52
GCD of two numbers is: 2

GCD of two numbers using for loop

public class GCDUsingForLoop
{
   public static void main(String[] args)
   {
      int number1 = 97, number2 = 177;
      // initially set gcd
      int gcd = 1;
      for(int a = 1; a <= number1 && a <= number2; ++a)
      {
         // checking if integer variable a 
         // divides both integer variables number1 and number2
         if(number1 % a == 0 && number2 % a == 0)
            gcd = a;
      }
      System.out.println("GCD of " + number1 + " and " + number2 + " is " + gcd);
   }
}

Output:

GCD of 97 and 177 is 1

In the above program first two numbers are stored in integer variables number1 and number2.

In the next step for loop is executed until integer variable ‘a’ is less than two variables number1 and number2. Then all numbers between 1 and smallest of two numbers are repeated to find GCD of two numbers.

Now if both number1 and number2 are divisible by variable ‘a’, gcd is set to variable ‘a’. This step is repeated until variable ‘a’ finds largest number which divides both integer variables number1 and number2 without remainder.