Efficiently Check for a Sum of Two Squares in Java

Last updated: November 17, 2025

Written by: Nikhil Bhargav

Reviewed by: David Martinez

Java Numbers

Math

Modern software architecture is often broken. Slow delivery leads to missed opportunities, innovation is stalled due to architectural complexities, and engineering resources are exceedingly expensive.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

With Orkes Conductor managed through Orkes Cloud, developers can focus on building mission critical applications without worrying about infrastructure maintenance to meet goals and, simply put, taking new products live faster and reducing total cost of ownership.

Try a 14-Day Free Trial of Orkes Conductor today.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

Try a 14-Day Free Trial of Orkes Conductor today.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

Try a 14-Day Free Trial of Orkes Conductor today.

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.

1. Introduction

In this short tutorial, we’ll explore an efficient way to determine if we can express a given integer n as the sum of squares of two integers a and b. The most basic method to test this is a brute-force approach, but we find it inefficient in terms of time and memory. Therefore, we resort to elementary number theory principles, specifically Fermat’s theorem on the sum of two squares, and develop a mathematically grounded, faster, and more accurate solution.

2. Fermat’s Sum of Two Squares Theorem

Famous Mathematician, Pierre de Fermat, gave the following theorem:

A positive integer n can be expressed as a sum of two squares if and only if the prime factorization of n contains no prime p raised to an odd power, where p is of the form 4k + 3 for a positive integer k.

Let’s understand this with a few examples. For n = 19, we obtain its prime factorization as 19¹. The prime is 19, which can be written as 4(4) + 3. Its exponent is 1 (odd). According to the theorem, we cannot write 19 as a sum of two squares.

Now, let’s take n=225. Its prime factorization is 3² × 5². According to the theorem, we need to check all primes of the form (4k+3). We can write 3 as 4(0)+3, and its exponent is 2 (an even number). The other prime 5 is of the form 4(1)+1, so it imposes no restrictions. Since all primes of the form (4k+3) have even exponents, the theorem guarantees that 225 can be written as the sum of two squares (indeed, 12² + 9² = 144 + 81 = 225).

3. Implementation

Moving ahead, we implement the method NumberAsSumOfTwoSquares() to test if we can write a given integer as the sum of two squares:

public static boolean isSumOfTwoSquares(int n) {
    private static final Logger LOGGER = LoggerFactory.getLogger(NumberAsSumOfTwoSquares.class);
    ...
};

The key idea is to avoid complete prime factorization and instead concentrate on finding the exponents of the 4k + 3 prime factors. First, we perform a quick check when input n is negative. Here, we log a warning and return false:

if (n < 0) {
    LOGGER.warn("Input must be non-negative. Returning false for n = {}", n);
    return false;
}

Next, we check for the trivial case n = 0. Since we can write 0 as the sum of two squares (0² + 0²), we return true:

if (n == 0) {
    return true;
}

Moving further, we check if the input n is even and reduce it to an odd number by successive division:

while (n % 2 == 0) {
    n /= 2;
}

Then, we iterate through odd numbers i (3, 5, 7, …) up to the square root of n and check if each i is a factor of n. On affirmative, we find its exponent (say, count) by counting how many times it divides n. Then, if the factor i is of the form 4k + 3. If the count is odd, we return false since it’s a violation:

for (int i = 3; i * i <= n; i += 2) {
    int count = 0;
    while (n % i == 0) {
        count++;
        n /= i;
    }
    if (i % 4 == 3 && count % 2 != 0) {
        LOGGER.debug("Failing condition: factor {} (form 4k+3) has odd exponent {}", i, count);
        return false;
    }
}

Once we end the loop, the remaining value of n > 1 is also a prime factor. So, we do a final check that if leftover n is of the form 4k + 3, it has an odd exponent (1), so we log a warning and return false:

if (n % 4 == 3) {
    LOGGER.debug("Failing condition: remaining factor {} is of form 4k+3", n);
    return false;
}

If we reach the end, we return true as n cleared all checks:

return true;

4. Verification

Let’s test the code in the above section using JUnit:

@Test
@DisplayName("Given input number can be expressed as a sum of squares, when checked, then returns true")
class NumberAsSumOfTwoSquaresUnitTest {
   ...
}

We test the affirmative case using the method givenNumberIsSumOfSquares_whenCheckIsCalled_thenReturnsTrue(). Here, the program returns true for the number that we can write the input integer n as the sum of the squares of two integers:

givenNumberIsSumOfSquares_whenCheckIsCalled_thenReturnsTrue() {
}

Here, we’re given input n for each run that can be written as the sum of the squares of two integers. When we call the method NumberAsSumOfTwoSquares(n), then we assertTrue when the method returns true for each invocation. For example, n=18 can be written as 18=3² + 3², so our program will return true, and our test run passes:

assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(0));
assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(8));
assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(50));
assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(45));
assertTrue(NumberAsSumOfTwoSquares.isSumOfTwoSquares(18));

5. Conclusion

In this article, we studied a classic number theory problem and solved it efficiently in Java. We applied Fermat’s theorem on sums of two squares to develop an algorithm that checks the prime factors of a number, rather than relying on a slow, brute-force search.

As always, the complete code for this article is available over on GitHub.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

Try a 14-Day Free Trial of Orkes Conductor today.

Orkes is the leading workflow orchestration platform built to enable teams to transform the way they develop, connect, and deploy applications, microservices, AI agents, and more.

Try a 14-Day Free Trial of Orkes Conductor today.

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.