# Prime Pairs With Target Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/prime-pairs-with-target-sum)
Canonical: https://scaleengineer.com/dsa/problems/prime-pairs-with-target-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
You are given an integer `n`. We say that two integers `x` and `y` form a prime number pair if:

* `1 <= x <= y <= n`
* `x + y == n`
* `x` and `y` are prime numbers

Return _the 2D sorted list of prime number pairs_ `[xi, yi]`. The list should be sorted in **increasing** order of `xi`. If there are no prime number pairs at all, return _an empty array_.

**Note:** A prime number is a natural number greater than `1` with only two factors, itself and `1`.

**Example 1:**

**Input:** n = 10
**Output:** [[3,7],[5,5]]
**Explanation:** In this example, there are two prime pairs that satisfy the criteria. 
These pairs are [3,7] and [5,5], and we return them in the sorted order as described in the problem statement.

**Example 2:**

**Input:** n = 2
**Output:** []
**Explanation:** We can show that there is no prime number pair that gives a sum of 2, so we return an empty array. 

**Constraints:**

* `1 <= n <= 106`

# Approaches
## Brute Force with Trial Division
This approach iterates through all possible values for the first number `x` from 2 up to `n/2`. For each `x`, it calculates the corresponding `y = n - x`. It then checks if both `x` and `y` are prime numbers using a simple trial division method.
**Time:** O(n * sqrt(n)). The main loop runs `n/2` times. Inside the loop, the `isPrime` checks take up to `O(sqrt(x))` and `O(sqrt(n-x))`. In the worst case, this is `O(sqrt(n))`. Thus, the total time is `O(n * sqrt(n))`. · **Space:** O(1) auxiliary space, excluding the space required for the output list.
**Pros:** Simple to understand and implement.; Very low memory usage.
**Cons:** Extremely inefficient due to repeated primality tests.; Will result in a 'Time Limit Exceeded' error for larger values of `n`.
### Explanation
The core idea is to check every potential pair `(x, y)` that sums to `n`. We can limit the search space for `x` to `[2, n/2]` because of the constraint `x <= y`. If `x > n/2`, then `y = n - x` would be less than `n/2`, which would violate the `x <= y` condition we are trying to maintain.

For each `x` in this range, we define a helper function `isPrime(num)`. This function checks for primality using the trial division method: it attempts to divide `num` by every integer from 2 up to the square root of `num`. If any division results in a remainder of 0, the number is composite (not prime).

If both `isPrime(x)` and `isPrime(n-x)` return true, we have found a valid prime pair. This pair is added to our result list. The final list of pairs is naturally sorted by `x` because our main loop iterates `x` in increasing order.

```java
class Solution {
    private boolean isPrime(int k) {
        if (k <= 1) {
            return false;
        }
        for (int i = 2; i * i <= k; i++) {
            if (k % i == 0) {
                return false;
            }
        }
        return true;
    }

    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> result = new ArrayList<>();
        for (int x = 2; x <= n / 2; x++) {
            int y = n - x;
            if (isPrime(x) && isPrime(y)) {
                result.add(Arrays.asList(x, y));
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Loop `x` from 2 to `n / 2`.
- Let `y = n - x`.
- Define a helper function `isPrime(k)` that checks for primality using trial division up to `sqrt(k)`.
- If `isPrime(x)` and `isPrime(y)` are both true, add the pair `[x, y]` to `result`.
- Return `result`.

## Sieve of Eratosthenes Pre-computation
This highly efficient approach avoids the costly repeated primality tests of the brute-force method. It pre-computes all prime numbers up to `n` using the Sieve of Eratosthenes. This allows for constant-time primality checks. After the pre-computation, it iterates through possible values for `x` and quickly finds the corresponding pairs.
**Time:** O(n * log(log(n))). The Sieve of Eratosthenes takes `O(n * log(log(n)))` time. The subsequent linear scan to find pairs takes `O(n)` time. The sieve is the dominant part. · **Space:** O(n) to store the `isPrime` boolean array.
**Pros:** Highly efficient and optimal for the given constraints.; A standard and powerful technique for problems involving primes within a fixed range.
**Cons:** Requires `O(n)` auxiliary space, which could be an issue for extremely large `n` (but is fine for `n <= 10^6`).
### Explanation
The core optimization is to solve the subproblem of primality testing efficiently for all numbers up to `n` at once.

1.  **Sieve of Eratosthenes**: We create a boolean array, `isPrime`, of size `n+1`. We initialize all entries from 2 to `n` as `true`. We then iterate from `p = 2` up to `sqrt(n)`. If `p` is still marked as prime, we iterate through its multiples (starting from `p*p`) and mark them as not prime. This process efficiently eliminates all composite numbers, leaving only primes marked as `true`.

2.  **Finding Pairs**: With the `isPrime` array populated, we can check if any number is prime in `O(1)` time. We then perform a single pass, iterating `x` from 2 up to `n/2`. For each `x`, we check if both `x` and its complement `y = n - x` are prime by looking up `isPrime[x]` and `isPrime[y]`.

3.  **Collecting Results**: If both `x` and `y` are prime, we add the pair `[x, y]` to our result list. Since we iterate `x` in increasing order, the resulting list of pairs will be sorted as required.

This combination of an efficient pre-computation step followed by a simple linear scan provides an optimal solution for the given constraints.

```java
class Solution {
    public List<List<Integer>> findPrimePairs(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int x = 2; x <= n / 2; x++) {
            if (isPrime[x]) {
                int y = n - x;
                if (isPrime[y]) {
                    result.add(Arrays.asList(x, y));
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Create a boolean array `isPrime` of size `n + 1` and initialize all entries to `true`.
- Mark `isPrime[0]` and `isPrime[1]` as `false`.
- Use the Sieve of Eratosthenes algorithm to mark all non-prime numbers up to `n` as `false` in the `isPrime` array.
- Initialize an empty list `result`.
- Loop `x` from 2 to `n / 2`.
- If `isPrime[x]` and `isPrime[n - x]` are both `true`, add the pair `[x, n-x]` to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> findPrimePairs(int n) {
    boolean[] primes = new boolean[n];
    Arrays.fill(primes, true);
    for (int i = 2; i < n; ++i) {
      if (primes[i]) {
        for (int j = i + i; j < n; j += i) {
          primes[j] = false;
        }
      }
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int x = 2; x <= n / 2; ++x) {
      int y = n - x;
      if (primes[x] && primes[y]) {
        ans.add(List.of(x, y));
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> findPrimePairs(int n) {
    bool primes[n];
    memset(primes, true, sizeof(primes));
    for (int i = 2; i < n; ++i) {
      if (primes[i]) {
        for (int j = i + i; j < n; j += i) {
          primes[j] = false;
        }
      }
    }
    vector<vector<int>> ans;
    for (int x = 2; x <= n / 2; ++x) {
      int y = n - x;
      if (primes[x] && primes[y]) {
        ans.push_back({x, y});
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]: primes = [True] * n for i in range(2, n): if primes[i]: for j in range(i + i, n, i): primes[j] = False ans = [] for x in range(2, n // 2 + 1): y = n - x if primes[x] and primes[y]: ans . append([x, y]) return ans

```