Sum of Primes Between Number and Its Reverse - Solution & Explanation

Problem Overview: You are given an integer n. Reverse its digits to get another number rev. The task is to compute the sum of all prime numbers in the range between min(n, rev) and max(n, rev). The main challenge is efficiently identifying primes across that range.

Approach 1: Brute Force Primality Check (O(k * sqrt(k)) time, O(1) space)

Compute the reversed value of n, then determine the interval [L, R] where L = min(n, rev) and R = max(n, rev). Iterate through every number in this range and run a primality test for each value. A typical check tries dividing the number by all integers from 2 to sqrt(x). If no divisor is found, add it to the running sum. This method is straightforward and works well when the interval is small, but repeated square‑root checks make it slow for larger ranges.

Approach 2: Precompute Using Sieve of Eratosthenes (O(R log log R) time, O(R) space)

Instead of checking each number independently, generate all primes up to R using the Sieve of Eratosthenes. Create a boolean array where each index represents whether the number is prime. Start from 2, mark multiples as composite, and continue until sqrt(R). Once the sieve is built, iterate from L to R and sum values whose sieve entry is still marked prime. This avoids repeated factor checks and dramatically improves performance when the range is large. The sieve approach is a classic technique from number theory and math problems involving repeated prime queries.

Approach 3: Segmented Sieve for Large Ranges (O((R-L+1) log log R) time, O(R-L+1) space)

If R can be extremely large but the interval size (R-L) is manageable, a segmented sieve becomes more memory efficient. First compute primes up to sqrt(R). Then create a local boolean array representing only the interval [L, R]. Use the previously computed primes to mark multiples within this segment. Remaining unmarked numbers are prime and can be summed directly. This method avoids allocating a full sieve up to R and is commonly used in competitive programming when dealing with big numeric ranges.

Recommended for interviews: The Sieve of Eratosthenes approach is typically the expected solution. Starting with the brute force method shows you understand primality testing, but moving to the sieve demonstrates stronger algorithmic thinking and familiarity with efficient prime generation techniques. It reduces repeated work and keeps the runtime near linear relative to the range size.