Finding Greatest Common Divisor in Java

Last updated: January 4, 2026

Written by: baeldung

Reviewed by: Rui Vilao

Algorithms

Recursion

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Distributed systems often come with complex challenges such as service-to-service communication, state management, asynchronous messaging, security, and more.

Dapr (Distributed Application Runtime) provides a set of APIs and building blocks to address these challenges, abstracting away infrastructure so we can focus on business logic.

In this tutorial, we'll focus on Dapr's pub/sub API for message brokering. Using its Spring Boot integration, we'll simplify the creation of a loosely coupled, portable, and easily testable pub/sub messaging system:

>> Flexible Pub/Sub Messaging With Spring Boot and Dapr

1. Overview

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.

2. Brute Force

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.

3. Euclid’s Algorithm

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.

4. Stein’s Algorithm or Binary GCD Algorithm

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ⁿ) * n2. Here, n is the number of times 2 is found common in n1 and n2 while performing step 2:

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₂n1)²) whereas. when n1 < n2, it is O((log₂n2)²).

5. Conclusion

In this tutorial, we looked at various methods for calculating the GCD of two numbers. We also implemented these in Java and had a quick look at their complexity.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.