GCD - Greatest Common Divisor - Euclidean Algorithm

Again, as always the intent of this site is to help us understand the algorithm, implement it in our own terms, rather than providing the most optimal implementation of an algorithms. This way of learning an algorithm helps us understand it and remember the implementation for a much longer time.

Greatest common divisor (gcd) of two or more integers, is the largest positive integer that divides both these numbers without a remainder. 

For example, the GCD of 8 and 12 is 4.

Brute force GCD algorithm :

Say we are given 2 numbers and asked to find the gcd of the same, say the numbers are 54 & 24 (Example citied in wikipedia)

Thus the divisors of 54 are:

1, 2, 3, 6, 9, 18, 27, 54

Similarly, the divisors of 24 are:

1, 2, 3, 4, 6, 8, 12, 24

The numbers that are common between these two divisor are

1, 2, 3, 4, 6,

Of the above the greatest of these is 6. Hence the greatest common divisor of 54 and 24 is 6

     gcd (54, 24) = 6

 Lets try and implement the above brute force algorithm

    private int bruteForceGCD(int n1, int n2) {
        List<Integer> firstDivisor = new ArrayList<>();
        List<Integer> secondDivisor = new ArrayList<>();

        // Get all the divisor of number 2
        for (int i = 2; i <= n1; i++) {
            if ((n1 % i) == 0) {
                firstDivisor.add(i);
            }
        }

        // Get all the divisor of number 2
        for (int i = 2; i <= n2; i++) {
            if ((n2 % i) == 0) {
                secondDivisor.add(i);
            }
        }

        //Find the max divisor that is common in both the list
        //Not an optimal code - for explanation only
        int maxDivisor = 1;
        for (int elem : firstDivisor) {
            if (secondDivisor.contains(elem) &&
                elem > maxDivisor) {
                maxDivisor = elem;
            }
        }

        return maxDivisor;
    }

Euclidean Algorithm

The Euclidean Algorithm for finding GCD(N1, N2) is as follows:

1. If N1 = 0 then GCD(N1, N2) = N2, since the GCD(0, N2) = N2, and we can stop.  
2. If N2 = 0 then GCD(N1, N2) = N1, since the GCD(N1, 0)= N1, and we can stop.  
3. If both N1 & N2 are non zero numbers, then we find the largest of these 2 numbers and rewrite the large number in terms of the small number
•      largestNumber = smallestNumber * Q + remainder
4.  The Euclidean algorithm states that  GCD(N1, N2) is same as GCD(smallestNumber, remainder)
5.  So when do we stop ? We stop at any instance the reminder is 0

Ok lets try and implement the above algorithm block by block which matches the above description of the algorithm

//Note optimized version - lot of unnecessary steps

private int euclideanGCD(int n1, int n2) {
        if (n1 == 0) {
            return n2;
        }
        
        if(n2 == 0) {
            return n1;
        }
        
        int largest = n1 > n2 ? n1 : n2;
        int smallest = n1 < n2 ? n1 : n2;
        
        int reminder = largest % smallest;
        
        if(reminder == 0) {
            return smallest;
        }
        
        return euclideanGCD(smallest, reminder);
    }

In reality there is no need for us to distinguish or identify the large number and small number. As an optimization, always assume the second argument as the small number, it should still work

Lets work this sample to understand how it works, Say we have 2 numbers 24 and 54 - We can try these 2 cases

Case 1 :  n1 = 24 and n2 = 54

We are going to assume that n2 is the smallest without looking at the value

In this case we first calculate = (24 mod 54) - We get 0 as quotient and 24 as remainder

So the subsequent call of this case gets converted to

 gcd (54, 24)

i.e

gcd (24, 54) becomes
gcd (smallNumber, remainder) after first execution, which is nothing but
gcd (54, 24)


Case 2 :  n1 = 54 and n2 = 24

 This is a straight forward case since we assumed n2 as smallest number it happen to match the values we received

Hence the above algorithm can written in a optimized way as

(Note : The same argument applies why we are checking for '0' for only one number - I leave it to you to work it out)

    private  int optimizedGCD(int n1, int n2) {
        if (n2 == 0) {
            return n1;
        }
        return optimizedGCD(n2, n1 % n2);
    }