2761. Prime Pairs With Target Sum
IntuitionWe need to find pairs of prime numbers whose sum equals n. This requires efficiently identifying prime numbers within a given range.ApproachUse the Sie
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need to find pairs of prime numbers whose sum equals n. This requires efficiently identifying prime numbers within a given range.
# Approach
<!-- Describe your approach to solving the problem. -->
Use the Sieve of Eratosthenes to precompute prime numbers up to n.
Iterate over potential values of x and check if y = n - x is also prime.
Store valid pairs in a sorted list and return the result.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
o(n)
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
o(n)
# Code
```cpp []
class Solution {
public:
    vector<vector<int>> findPrimePairs(int n) {
        vector<vector<int>> ans;
        vector<int> once(n, 0);

        for (int i = 2; i < n; i++) {
            if (once[i] == 0) {
                for (int j = i * 2; j < n; j += i) {
                    once[j] = 1;
                }
            }
        }
        int i = 2;
        int j = n - 2;
        while (i <= j) {
            if (once[i] == 0 && once[j] == 0) {
                if (i + j == n) {
                    ans.push_back({i, j});
                }
            }
            i++;
            j = n - i;
        }
        return ans;
    }
};
```
['C++']