Sieve of Eratosthenes + Two Sum | C++
Intuition\nSince we need to find all primes pairs, why not find all primes with sieve and apply Two sum on it.\n# Approach\nStore all primes Numbers in a vector
# Intuition\nSince we need to find all primes pairs, why not find all primes with sieve and apply Two sum on it.\n# Approach\nStore all primes Numbers in a vector, then a single for loop to check if the sum can be formed. Finally sort the answer vector and return\n\n# Complexity\n- Time complexity:\nO(log(log(n))) for sieve\nO(n) for finding all sums\nand another added complexity for finally sorting the answer vector\n\n- Space complexity:\nO(primes till n) for storing prime numbers\nand more space for storing indices of previously visited element to find sum worst case : O(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> primesTillN(const int& n){\n        vector<bool> sieve(n+1,true);\n\n        sieve[0] = sieve[1] = false;\n\n        for(int i = 2 ; i*i < n + 1 ; i++){\n            if(sieve[i] == true){\n                int j = i*i;\n                while(j < n + 1){\n                    sieve[j] = false;\n                    j += i;\n                }\n            }\n        }\n        vector<int> primes;\n        for(int i = 2 ; i < sieve.size() ; i++){\n            if(sieve[i] == true){\n                primes.push_back(i);\n            }\n        }\n        return primes;\n    }\n\n    vector<vector<int>> findPrimePairs(const int& n) {\n        vector<int> primes = primesTillN(n);\n        vector<vector<int>> ans;\n\n        int temp = n;\n\n        unordered_map<int,int> m;\n\n        for(int i = 0 ; i < primes.size() ; i++){\n            m[primes[i]] = i;\n            if(m.find(n - primes[i]) != m.end()){\n                ans.push_back({n-primes[i],primes[i]});\n            }\n        }\n\n        sort(ans.begin(),ans.end());\n\n        return ans;   \n    }\n};\n```
['C++']