How to find gcd in java - Java Program to Find GCD of two Numbers

How to find gcd in java: Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Program to Find GCD of two Numbers

GCD of two numbers in java: In this article, we will see multiple ways to find the GCD(Greatest Common Divisor) of two numbers.

In mathematics , the greatest common divisor of two or more integers, which are not all zero is the largest positive integer.

For example:

24 = 2*2*2*3
18 = 2*3*3
GCD = 2*3 = 6.

To find GCD of Two Numbers using a while loop with the if-else statement
To find GCD of two numbers using for loop and if statement
GCD for both positive and negative number
GCD of more than two (or array) numbers
To find GCD using the modulo operator

Method 1 : To find GCD of Two Numbers using a while loop with the if-else statement

GCD program in java: We can use while loop with if-else statement to find GCD of two number.

Approach:

First, assign the values for int n1 and n2 for which you want to find GCD.
Then the smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding the larger integer.
This process is continued until n1and n2 are equal.

Program:

class Main 
{
  public static void main(String[] args) {

    
    int n1 = 81, n2 = 153;
    
    while(n1 != n2) {
    
      if(n1 > n2) {
        n1 -= n2;
      }
      
      else {
        n2 -= n1;
      }
    }

    System.out.println("GCD: " + n1);
  }
}

Output:

GCD: 9

Method 2 : To find GCD of two numbers using for loop and if statement

Java gcd code: We can use for loop with if-statement to find GCD of two numbers.

Approach:

Two numbers whose GCD are to be found are stored in n1 and n2
Then, a for loop is executed until i is less than both n1 and n2. This way, all numbers between 1 and the smallest of the two numbers are iterated to find the GCD.
If both n1and n2 are divisible by i, gcd is set to the number. This goes on until it finds the largest number (GCD) which divides both n1 and n2 without remainder.

Program:

class Main 
{
  public static void main(String[] args) 
  {

    
    int n1 = 81, n2 = 153;
    
    int gcd = 1;

    for (int i = 1; i <= n1 && i <= n2; ++i) 
    {

      
      if (n1 % i == 0 && n2 % i == 0)
        gcd = i;
    }

    System.out.println("GCD of " + n1 +" and " + n2 + " is " + gcd);
  }
}

Output:

GCD of 81 and 153 is 9

Method 3: GCD for both positive and negative number

GCd function java: In this approach we will see GCD for both positive and negative number.

Approach:

first, assign the values for int n1 and n2 for which you want to find GCD.
Then the smaller integer is subtracted from the larger integer, and the result is assigned to the variable holding larger integer.
This process is continued until n1 and n2 are equal.

Program:

class Main
{
  public static void main(String[] args) 
{

    int n1 = 81, n2 = -153;

   
    n1 = ( n1 > 0) ? n1 : -n1;
    n2 = ( n2 > 0) ? n2 : -n2;

    while(n1 != n2) {
        
      if(n1 > n2) {
        n1 -= n2;
      }
      
      else {
        n2 -= n1;
      }
    }
    
    System.out.println("GCD: " + n1);
  }
}

Output:

GCD:9

Method 4 : GCD of more than two (or array) numbers

Java gcd function: In this we will see how to get GCD of more than 2 numbers.

Approach:

A class named Demo contains the main function that takes in two values.
If the first value is 0, the second value is returned as output. Otherwise, a recursive function is written that computes the greatest common divisor of the two elements.
Next, another static function is defined that takes an array and another integer value as a parameter.
The first element of the array is assigned to a variable named ‘result’ and a ‘for’ loop iterates over elements from 1 to the integer value that was passed as a parameter to the function.
This output is assigned to the ‘result’ variable itself. If the value of ‘result’ is 1, then the output is 1, otherwise, the value of ‘result’ is returned.

Program:

public class Main
{
   static int gcd_of_nums(int val_1, int val_2)
   {
      if (val_1 == 0)
      return val_2;
      return gcd_of_nums(val_2 % val_1, val_1);
   }
   static int find_gcd(int arr[], int no){
      int result = arr[0];
      for (int i = 1; i < no; i++){
         result = gcd_of_nums(arr[i], result);
         if(result == 1){
            return 1;
         }
      }
      return result;
   }
   public static void main(String[] args)
   {
      int my_arr[] = { 7, 49, 177, 105, 119, 42};
      int no = my_arr.length;
      System.out.println("The GCD of the elements in the array is ");
      System.out.println(find_gcd(my_arr, no));
   }
}

Output:

The GCD of the elements in the array is 1

Method 5: To find GCD using the modulo operator

gcd java: We can use for loop with if-statement to find GCD of two numbers.

Approach:

First, we have defined a recursive function named GCD().
It parses two parameters a and b of type int.
If the second number (b) is equal to 0, the method returns, and as GCD else returns a%b.

Program:

public class Main 
{   
    public static void main(String[] args)   
    {   
        int a = 112, b = 543;   
        System.out.println("GCD of " + a +" and " + b + " is " + GCD(a, b));   
        }  
          
        static int GCD(int a, int b)   
        {   
        if (b == 0)   
        return a;     
        return GCD(b, a % b);   
    }   
}

Output:

GCD of 112 and 543 is 1

Get started with learning the programming language Java from beginner to experienced level by referring to our collection of Java Programs with Source Code and become a pro in the subject.

Related Java Decision Making and Loop Programs: