GCD of N Numbers in Java

GCD of N Numbers in Java | Array Programs in Java – 17 | In the previous Java program, we developed programs to sort array elements and find the reverse of an array. 

Program Description:- Write a Java program to find the GCD of N numbers or more than two numbers. The GCD of three or more numbers can be calculated by repeatedly taking the GCD of pairs of numbers.

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)

The GCD of N numbers is also calculated by finding the prime factors, the GCD of N numbers is equal to the prime factors common to all the numbers.

For an array of numbers, the GCD can be calculated as,

// initialize result with first number in the array
result = arr[0];
// loop
for i = 1 to n-1
result = findHCF(result, arr[i])

Procedure to find GCD or HCF of two numbers,

1) Take two numbers
2) Find the largest & smallest number among them
3) Subtract the smallest number value from the largest number
4) Repeat this process until both numbers become equal

The GCD or HCF of two numbers in Java can be calculated as,

// Java method to find GCD or HCF of two numbers
public static int findHCF(int num1, int num2) {
  while(num1 != num2) {
    if(num1 > num2) 
       num1 = num1 - num2;
    else
       num2 = num2 - num1;
  }
  return num1;
}

Java Program to Find GCD of N Numbers

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

    // variables
    int size = 0;
    int arr[] = null;
    int result = 0;
    
    // create Scanner class object to read input
    Scanner scan = new Scanner(System.in);
    
    // read size
    System.out.print("Enter total numbers: ");
    size = scan.nextInt();
    
    // declare array
    arr = new int[size];
    
    // read numbers
    System.out.println("Enter numbers: ");
    for(int i=0; i<size; i++) {
      arr[i] = scan.nextInt();
    }
    
    // assign first number to result
    result = arr[0];
    
    // loop
    for(int i=1; i<size; i++) {
      result = findHCF(result, arr[i]);
    }
    
    // display result
    System.out.println("GCD = " + result);

    // close Scanner
    scan.close();
  }

  public static int findHCF(int num1, int num2) {
    while (num1 != num2) {
      if (num1 > num2)
        num1 = num1 - num2;
      else
        num2 = num2 - num1;
    }
    return num1;
  }
}

Output for the different test cases:-

Enter total numbers: 3
Enter numbers:
10 15 25
GCD = 5

Enter total numbers: 5
Enter numbers:
9 36 25 5 12
GCD = 1

In this program, first, we have taken the required variables:- size, arr, and result. The size variable will hold the number of elements in the array, the arr variable represents the array, and the result variable will hold the final result.

Then we created an object of the Scanner class to read input values from the end-user. To read input from the end-user you can also use BufferedReader class. The array size should be taken before declaring the array. After declaring the array, take numbers i.e. elements of the array. The first number will be assigned to the result variable. Now, use the loop to repeat the process, and calculate the result by repeatedly taking the GCD of pairs of numbers.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!