Two Sum
We can use two pointers to find all pais that sum to n, like in 1. Two Sum.\n\nTo do that, we need to prepare an array with prime numbers. We can use Sieve of E
We can use two pointers to find all pais that sum to `n`, like in [1. Two Sum](https://leetcode.com/problems/two-sum/).\n\nTo do that, we need to prepare an array with prime numbers. We can use Sieve of Eratosthenes to do it efficiently.\n\nNote that we populate primes into global `p` vector once, and then reuse for all test cases.\n\n**C++**\n```cpp\nvector<int> p;\nclass Solution {\npublic:\nvector<vector<int>> findPrimePairs(int n) {\n    if (p.empty()) {\n        bool sieve[1000000] = {};\n        for (long long i = 2; i < 1000000; ++i)\n            if (!sieve[i]) {\n                p.push_back(i);\n                for (long long j = i * i; j < 1000000; j += i)\n                    sieve[j] = true;\n            }\n    }\n    vector<vector<int>> res;\n    int i = 0, j = upper_bound(begin(p), end(p), n) - begin(p) - 1;\n    while (i <= j) {\n        if (p[i] + p[j] == n) {\n            res.push_back({p[i], p[j]});\n            ++i, --j;\n        }\n        else if (p[i] + p[j] < n)\n            ++i;\n        else\n            --j;\n    }\n    return res;\n}\n```
['C']