Most Optimized Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(2 * NlogN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntypedef long long ll;\n\n#define ii ({ll a; cin >> a; a;})\n#define si ({string string_input; cin >> string_input; string_input;})\n#define vll vector<ll>\n#define vi vector<int>\n#define vvi vector<vector<int>>\n#define pb push_back\n\nll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }\nll lcm(ll a, ll b) { return a / gcd(a, b) * b; }\n\ntemplate <typename T>\nvoid dis(vector<T> &v) { for (auto &i : v) cout << i << " "; cout << "\\n"; }\n\ntemplate <typename T, size_t N>\nvoid show(T (&arr)[N]) { for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << "\\n"; }\n\nclass Solution {\n    vll primes;\n\n    void sieve(ll n){\n        vector<bool> isPrime(n+1, true);\n        for(ll p = 2; p <= n; p++){\n            if(isPrime[p]){\n                primes.push_back(p);\n                for(ll i = p*p; i <= n; i += p){\n                    isPrime[i] = false;\n                }\n            }\n        }\n        // dis(primes);\n    }\npublic:\n    vector<vector<int>> findPrimePairs(ll n) {\n        vvi ans;\n        sieve(n);\n        for(auto &x: primes){\n            if(x*2LL > n) break;\n            ll y = n-x;\n            if(binary_search(primes.begin(), primes.end(), y)){\n                ans.pb({(int)x, (int)y});\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']