**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

**>> CHECK OUT THE COURSE**

Last modified: August 11, 2019

In mathematics, the GCD of two integers, which are non-zero, is **the largest positive integer that divides each of the integers evenly.**

In this tutorial, we’ll look at three approaches to find the Greatest Common Divisor (GCD) of two integers. Further, we’ll look at their implementation in Java.

For our first approach, we iterate from 1 to the smallest number given and check whether the given integers are divisible by the index. **The largest index which divides the given numbers **is the GCD of the given numbers:

int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }

As we can see, the complexity of the above implementation is *O(min(n1, n2))* because we need to iterate over the loop for *n* times (equivalent to the smaller number) to find the GCD.

Second, we can use Euclid’s algorithm to find the GCD. Euclid’s algorithm is not only efficient but also easy to understand and easy to implement using recursion in Java.

Euclid’s method depends on two important theorems:

- First, if we subtract the smaller number from the larger number, the GCD doesn’t change –
**therefore, if we keep on subtracting the number we finally end up with their GCD** - Second, when the smaller number exactly divides the larger number, the smaller number is the GCD of the two given numbers.

Note in our implementation that we’ll use modulo instead of subtraction since it’s basically many subtractions at a time:

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

Also, note how we use *n2 *in *n1*‘s position and use the remainder in n2’s position in the recursive step of the algorithm*.*

Further,** the complexity of Euclid’s algorithm is O(Log min(n1, n2)) which is better as compared to the Brute Force method we saw before.**

Finally, we can use Stein’s algorithm, also **known as the Binary GCD algorithm**, to find the GCD of two non-negative integers. This algorithm uses simple arithmetic operations like arithmetic shifts, comparison, and subtraction.

Stein’s algorithm repeatedly applies the following basic identities related to GCDs to find GCD of two non-negative integers:

*gcd(0, 0) = 0, gcd(n1, 0) = n1, gcd(0, n2) = n2*- When
*n1*and*n2*are both even integers, then*gcd(n1, n2) = 2 * gcd(n1/2, n2/2)*, since 2 is the common divisor - If
*n1*is even integer and*n2*is odd integer, then*gcd(n1, n2) = gcd(n1/2, n2)*, since 2 is not the common divisor and vice versa - If
*n1*and*n2*are both odd integers, and*n1 >= n2*, then*gcd(n1, n2) = gcd((n1-n2)/2, n2)*and vice versa

We repeat steps 2-4 until *n1* equals *n2*, or *n1 = 0*. The GCD is *(2 ^{n}) * n2*. Here,

int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }

We can see that we use arithmetic shift operations in order to divide or multiply by 2. Further, we use subtraction in order to reduce the given numbers.

**The complexity of Stein’s algorithm when n1 > n2 is O((log_{2}n1)^{2}) whereas. when n1 < n2, it is O((log_{2}n2)^{2}).**

In this tutorial, we looked at various methods for calculating the GCD of two numbers. Besides, we implemented them in Java and looked at their complexity.

The full source code of our examples here is, as always, over on GitHub.

## Leave a Reply