Problem Description

Given an integer n, you need to find all pairs of prime numbers (x, y) that satisfy the following conditions:

• Both x and y must be prime numbers
• x + y must equal n
• 1 <= x <= y <= n

Return a 2D list containing all valid prime number pairs [x, y]. The list should be sorted in increasing order of x. If no valid prime pairs exist, return an empty array.

A prime number is defined as a natural number greater than 1 that has exactly two factors: 1 and itself.

For example, if n = 12, the valid prime pairs would be [[5, 7]] because:

• 5 and 7 are both prime numbers
• 5 + 7 = 12
• 5 <= 7

The solution uses the Sieve of Eratosthenes algorithm to efficiently find all prime numbers up to n. It creates a boolean array primes where primes[i] indicates whether i is prime. Then it iterates through all possible values of x from 2 to n//2, calculates y = n - x, and checks if both x and y are prime. If they are, the pair [x, y] is added to the result.

The reason for only checking x up to n//2 is to ensure x <= y. Since x + y = n, when x > n//2, we would have y < x, which violates the constraint x <= y.

Intuition

The key insight is that we need to find two prime numbers that sum to n. Since we're looking for pairs (x, y) where x + y = n, once we choose a value for x, the value of y is automatically determined as y = n - x.

This transforms our problem from finding pairs to simply iterating through possible values of x and checking if both x and its complement n - x are prime.

To avoid duplicate pairs and ensure x <= y, we only need to check values of x up to n/2. Why? Because if x > n/2, then y = n - x < n/2, which means y < x. This would give us the same pair but in reverse order, which we want to avoid.

The most time-consuming part would be checking if numbers are prime. If we checked primality for each number individually using trial division, it would be inefficient. Instead, we can pre-compute all prime numbers up to n using the Sieve of Eratosthenes algorithm. This gives us O(1) lookup time to check if any number is prime.

The Sieve works by initially assuming all numbers are prime, then systematically marking multiples of each prime as composite. After this preprocessing, we have a boolean array where we can instantly check if any number up to n is prime.

With this setup, the solution becomes straightforward:

1. Pre-compute all primes up to n
2. For each potential x from 2 to n/2, check if both x and n - x are prime
3. If both are prime, add the pair [x, n - x] to our answer

Learn more about Math patterns.

Solution Approach

The solution consists of two main phases: preprocessing prime numbers and finding valid pairs.

Phase 1: Prime Number Preprocessing using Sieve of Eratosthenes

We create a boolean array primes of size n where primes[i] indicates whether i is prime. Initially, we assume all numbers are prime by setting all values to True.

primes = [True] * n

Then we implement the Sieve of Eratosthenes:

• Start iterating from i = 2 (the smallest prime)
• If primes[i] is True, then i is prime
• Mark all multiples of i (starting from 2i, then 3i, 4i, etc.) as False since they're composite
• Continue this process for all numbers up to n

for i in range(2, n):
    if primes[i]:
        for j in range(i + i, n, i):
            primes[j] = False

The inner loop range(i + i, n, i) generates multiples of i starting from 2i up to n-1 with step size i.

Phase 2: Finding Prime Pairs

After preprocessing, we enumerate all possible values of x:

• We iterate x from 2 to n // 2 + 1 (inclusive of n // 2)
• For each x, we calculate y = n - x
• Check if both x and y are prime using our preprocessed array
• If both are prime, add the pair [x, y] to our answer

ans = []
for x in range(2, n // 2 + 1):
    y = n - x
    if primes[x] and primes[y]:
        ans.append([x, y])

The range (2, n // 2 + 1) ensures:

• We start from 2 (the smallest prime)
• We stop at n // 2 to maintain x <= y
• The pairs are automatically sorted by x since we iterate in increasing order

Time Complexity: O(n log log n) for the Sieve of Eratosthenes + O(n) for finding pairs = O(n log log n)

Space Complexity: O(n) for the primes array

Example Walkthrough

Let's walk through the solution with n = 12.

Step 1: Create Prime Sieve

First, we create a boolean array primes of size 12 and initialize all values to True:

Index: 0  1  2  3  4  5  6  7  8  9  10 11
Value: T  T  T  T  T  T  T  T  T  T  T  T

Step 2: Apply Sieve of Eratosthenes

Starting with i = 2 (prime):

• Mark multiples of 2: positions 4, 6, 8, 10 become False

With i = 3 (prime):

• Mark multiples of 3: positions 6, 9 become False (6 already marked)

With i = 4: Already marked as False, skip

With i = 5 (prime):

• Mark multiples of 5: position 10 already False

With i = 6: Already marked as False, skip

With i = 7 (prime):

• No multiples within range to mark

Continue until i = 11...

Final primes array:

Index: 0  1  2  3  4  5  6  7  8  9  10 11
Value: F  F  T  T  F  T  F  T  F  F  F  T

Primes are: 2, 3, 5, 7, 11

Step 3: Find Prime Pairs

Iterate x from 2 to n // 2 = 6:

• x = 2: y = 12 - 2 = 10

  • Is 2 prime? Yes (primes[2] = True)
  • Is 10 prime? No (primes[10] = False)
  • Don't add this pair

• x = 3: y = 12 - 3 = 9

  • Is 3 prime? Yes (primes[3] = True)
  • Is 9 prime? No (primes[9] = False)
  • Don't add this pair

• x = 4: y = 12 - 4 = 8

  • Is 4 prime? No (primes[4] = False)
  • Skip

• x = 5: y = 12 - 5 = 7

  • Is 5 prime? Yes (primes[5] = True)
  • Is 7 prime? Yes (primes[7] = True)
  • Add pair [5, 7] to result

• x = 6: y = 12 - 6 = 6

  • Is 6 prime? No (primes[6] = False)
  • Skip

Result: [[5, 7]]

The algorithm correctly identifies that only the prime pair (5, 7) sums to 12.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log log n)

The time complexity is dominated by the Sieve of Eratosthenes algorithm used to find all prime numbers up to n.

• The outer loop runs from 2 to n, iterating O(n) times.
• For each prime number i, the inner loop marks its multiples as non-prime, running n/i times.
• The total number of operations is approximately n/2 + n/3 + n/5 + n/7 + ... = n × (1/2 + 1/3 + 1/5 + 1/7 + ...) for all primes up to n.
• The sum of reciprocals of primes up to n is O(log log n), making the sieve portion O(n log log n).
• The second loop to find prime pairs runs O(n/2) times with O(1) operations per iteration, contributing O(n) time.
• Overall time complexity: O(n log log n) + O(n) = O(n log log n).

Space Complexity: O(n)

• The primes boolean array stores n elements, requiring O(n) space.
• The ans list stores the prime pairs, which in the worst case could be O(n) pairs (though typically much fewer).
• Additional variables use constant space O(1).
• Overall space complexity: O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds Error

One of the most common mistakes is not handling edge cases properly when initializing the is_prime array, especially for small values of n.

Problematic Code:

is_prime = [True] * n
is_prime[0] = False  # IndexError when n = 0
is_prime[1] = False  # IndexError when n = 0 or n = 1

Solution: Always check bounds before accessing array indices:

is_prime = [True] * n
if n > 0:
    is_prime[0] = False
if n > 1:
    is_prime[1] = False

2. Incorrect Range in Sieve Implementation

Another pitfall is using an incorrect range when marking composite numbers, which can lead to incomplete prime detection.

Problematic Code:

# Starting from i * i instead of i * 2
for j in range(i * i, n, i):  # May miss some composites
    is_prime[j] = False

While starting from i * i is a valid optimization (since smaller multiples have already been marked), it requires careful handling of integer overflow for large values. Starting from i * 2 is safer and clearer.

Solution:

for j in range(i * 2, n, i):
    is_prime[j] = False

3. Off-by-One Error in Finding Pairs

Forgetting to include n // 2 in the range when n is even can cause missing valid pairs.

Problematic Code:

for x in range(2, n // 2):  # Excludes n//2
    y = n - x
    # This misses the pair where x = y = n/2 when n is even

Solution:

for x in range(2, n // 2 + 1):  # Includes n//2
    y = n - x

4. Not Handling n < 2 Properly

When n < 2, there cannot be any valid prime pairs since the smallest prime is 2.

Problematic Code:

def findPrimePairs(self, n: int) -> List[List[int]]:
    is_prime = [True] * n  # Creates empty array when n = 0
    # Rest of the code...

Solution: Add an early return for invalid cases:

def findPrimePairs(self, n: int) -> List[List[int]]:
    # No valid prime pairs possible for n < 4
    if n < 4:
        return []
  
    is_prime = [True] * n
    # Rest of the code...

5. Memory Inefficiency for Large n

Creating a boolean array of size n can be memory-intensive for very large values of n.

Alternative Approach for Memory Optimization: Instead of storing all primes, generate them on-the-fly or use a set to store only actual primes:

def findPrimePairs(self, n: int) -> List[List[int]]:
    # Generate set of primes up to n
    primes_set = set()
    is_prime = [True] * n
  
    # Sieve to identify primes
    for i in range(2, n):
        if is_prime[i]:
            primes_set.add(i)
            for j in range(i * 2, n, i):
                is_prime[j] = False
  
    # Find pairs using the set
    result = []
    for x in primes_set:
        if x > n // 2:
            break
        y = n - x
        if y in primes_set:
            result.append([x, y])
  
    return sorted(result)  # Sort by x