Teachers

How to find the Greatest common divisor of an integer array in java

In this post Im going to illustrate very simple algorithm to find the Greatest Common Divisor (GCD)  of set of integers (an array) using java.

• In this algorithm we first find the smallest integer in the int array. 
• Then we get the modulus for each element in the numbers of the array by dividing smallest integer and add all those modulus together. 
• After processing each element in the array we check if the total of modulus is equals to 0.  If it is equal to 0 then the GCD is  current smallest value if that total is not equals 0 we deduct 1 from the previous smallest value and do the same computation. 
• The algorithm will continue with  the same operations until total of modulus becomes 0 or until smallest integer is 2.
• If there is any GCD, algorithm will return it or otherwise it will return -1.

See the following implementation of the algorithm.

public class GCD {

    public static int findGcd(int... numbers) {

        //Find the smallest integer in the number list
        
        int smallest = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < smallest) {
                smallest = numbers[i];
            }
        }

        //Find the GCD
        while (smallest > 1) {
            
            int counter = 0;
            int modTot = 0;
            
            while (counter < numbers.length) {

                modTot += numbers[counter] % smallest;
                counter++;

            }

            if (modTot == 0) {
                //Return the gcd if any
                return smallest;
            }

            //System.out.print(" "+ smallest);
            smallest--;

        }
        //return -1 if there is no gcd
        return -1;
    }

    public static void main(String[] x) {
        System.out.println("The GCD of 15 18 42 108 : "+GCD.findGcd(new int[]{15, 18, 42,108}));
    }
}

Here is the output for 15, 18, 42 and 108


Here is the output for 3,7 and 12