TheAlgorithms/Java · error · RuntimeException

GCD cannot be found.

Error message

GCD cannot be found.

What it means

Thrown by PollardRho's factorization when the algorithm's GCD loop terminates with d == number, meaning Pollard's rho failed to find a non-trivial factor. This happens for prime inputs (no factor exists other than the number itself) or when the cycle-detection walk collapses without separating a factor. The library signals failure via RuntimeException rather than returning a meaningless value.

Source

Thrown at src/main/java/com/thealgorithms/maths/PollardRho.java:76

     * @return Integer non-trivial factor of number
     * @throws RuntimeException object if GCD of given number cannot be found
     */
    static int pollardRho(int number) {
        int x = 2;
        int y = 2;
        int d = 1;
        while (d == 1) {
            // tortoise move
            x = g(x, number);

            // hare move
            y = g(g(y, number), number);

            // check GCD of |x-y| and number
            d = GCD.gcd(Math.abs(x - y), number);
        }
        if (d == number) {
            throw new RuntimeException("GCD cannot be found.");
        }
        return d;
    }
}

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Run a primality test (e.g., PrimeCheck.isPrime) first and handle primes separately — PollardRho is for composite factorization.
2. Retry with a different polynomial/seed; Pollard's rho is probabilistic and a different g(x) often succeeds.
3. Fall back to trial division for small numbers or a deterministic factorization method.

Example fix

// before
int f = PollardRho.pollardRho(n);

// after
if (PrimeCheck.isPrime(n)) {
    throw new IllegalArgumentException("n is prime, no non-trivial factor: " + n);
}
int f = PollardRho.polliderRho(n); // call only on composites

if (PrimeCheck.isPrime(n)) {
    throw new IllegalArgumentException("n is prime, no non-trivial factor: " + n);
}
int f = PollardRho.polliderRho(n);

try {
    int f = PollardRho.polliderRho(n);
} catch (RuntimeException e) {
    if ("GCD cannot be found.".equals(e.getMessage())) {
        // n is likely prime or rho failed; retry with different seed or fall back
    }
    throw e;
}

When it happens

Trigger: Calling the PollardRho factor method on a prime number, or on a composite where the random walk fails to find a proper divisor (a known probabilistic failure mode of Pollard's rho). The loop exits when d != 1, and the subsequent check d == number triggers the throw.

Common situations: Feeding a prime to PollardRho expecting a factorization; using PollardRho without a prior primality test; input is a small composite that the rho walk cannot split with the chosen polynomial; calling on 1 or a degenerate value.

Related errors

• Theta (angle) must be a finite number.
• Denominator cannot be 0
• Numbers array cannot be empty or null
• Input 'n' is too big to give accurate result.
• k must be between 1 and the size of the array

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/d9bb547fa9b86326. Report an issue: GitHub.