Explained - diff technique || Very simple and easy to understand
Approach\nThis problem can be converted to the typical two sum problem, where the elements are the primes number less then n. Solve this two sum if you have not
# Approach\nThis problem can be converted to the typical [two sum problem](https://leetcode.com/problems/two-sum/), where the elements are the primes number less then n. Solve this two sum if you have not done it before.\n\nNow to find the primes we can do it in two ways :\n## Solution 1:\nThis solution is a bit different then Sieve of Eratosthenes algo, lets discuss this first.\n \nHere we will keep on finding primes and use the same prime set to check if the next number is prime or not.\n\nFollowing solution beats 100% on memory as well as runtime. I know many of the folks argue that here the primes are evaluated only one due to which this is more optimised and this something more practical in real application developments.\n\n```\nunordered_set<int> st;\nvector<int> primes;\n\nclass Solution {\npublic:\n    void getPrimes(){\n        primes.push_back(2); primes.push_back(3); \n        for(int i = 6; i < 1000000; i += 6){\n            int f1 = 1, f2 = 1;\n            for(int j = 0; primes[j] <= sqrt(i+1) && j < primes.size(); ++j ){\n               if((i - 1) % primes[j] == 0) { f1 = 0; }\n               if((i + 1) % primes[j] == 0) { f2 = 0; }\n            }\n            if(f1) primes.push_back(i-1);\n            if(f2) primes.push_back(i+1);\n        }\n        for(auto p: primes) st.insert(p);\n    }\n   \n    vector<vector<int>> findPrimePairs(int n) {\n        if(st.size() == 0) getPrimes();\n        vector<vector<int>> ans;\n        for(int i = 0; i < primes.size() && primes[i] <= n/2; ++i){\n            if(st.find(n - primes[i]) != st.end()) {  ans.push_back({primes[i], n - primes[i]});  }\n        }\n        return ans;\n    }\n};\n```\n\n## Soltuion 2: Sieve of Eratosthenes\nFor more details : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes\n\nHere I have used the previous set and vector to evaluate two sum, but as we are evaluating all the values till n are prime or not, we can do this with out even using set. Here is a simple solution that do not use set : https://leetcode.com/problems/prime-pairs-with-target-sum/solutions/3706625/two-sum-sieve/\n\n```\nunordered_set<int> st;\nvector<int> primes;\n    \nclass Solution {\npublic:\n    void getPrimes(int n ){\n        vector<bool> isPrime(n, 1);\n        for(int i = 2; i <= sqrt(n); ++i){\n          if(isPrime[i]){\n            for(int j = i*i; j < n; j += i ) isPrime[j] = false;\n          }\n        }\n        for(int i = 2; i < isPrime.size(); ++i) {\n          if(isPrime[i]) { st.insert(i); primes.push_back(i); }\n        }\n    }\n\n    vector<vector<int>> findPrimePairs(int n) {\n        if(st.size() == 0) getPrimes(1000000); cout<<primes.size();\n        vector<vector<int>> ans;\n        for(int i = 0; i < primes.size() && primes[i] <= n/2; ++i){\n            if(st.find(n - primes[i]) != st.end()) {  ans.push_back({primes[i], n - primes[i]});  }\n        }\n        return ans;\n    }\n};\n```\n\nHere is an article of my last interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:\nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted\n\n\n
['C++']