# 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. 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;
// 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);

System.out.print("Enter total numbers: ");
size = scan.nextInt();

// declare array
arr = new int[size];

System.out.println("Enter numbers: ");
for(int i=0; i<size; i++) {
arr[i] = scan.nextInt();
}

// assign first number to result
result = arr;

// loop
for(int i=1; i<size; i++) {
result = findHCF(result, arr[i]);
}

// display result
System.out.println("GCD = " + result);

// close Scanner
scan.close();
}

// recursive method
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 calculated 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!