Easy Solution Using Sieve
Intuition\n Describe your first thoughts on how to solve this problem. \nWhenever there are a series of prime numbers required, the first thing that comes to mi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhenever there are a series of prime numbers required, the first thing that comes to mind is the sieve of eratosthenes and that is what I have used here. \nThe sieve filters oyt the prime numbers out of the composite numbers.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe find all the prime numbers upto $$n$$ (using the sieve) then iterate over the sieve to find all such pairs that sum up to $$n$$.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSince we are making use of sieve, we require an extra array of size $$n$$. Therefore, space complexity is $$O(n)$$.\n\n# Python3 Code\n```\nclass Solution:\n    def findPrimePairs(self, n: int) -> List[List[int]]:\n        ans = []\n        \n        prime = [True for _ in range(n+1)]\n        prime[0] = prime[1] = False\n        \n        for i in range(2, n+1):\n            if prime[i]:\n                j = i*i\n                \n                while j<=n:\n                    prime[j] = False\n                    j += i\n        for i in range(2,n):\n            if i+i>n: break\n            if prime[i] and prime[n-i]:\n                ans.append([i,n-i])\n        return ans\n    \n```\n# C++ Code\n```\n#include <vector>\n\nclass Solution {\npublic:\n    std::vector<std::vector<int>> findPrimePairs(int n) {\n        std::vector<std::vector<int>> ans;\n        \n        std::vector<bool> prime(n+1, true);\n        prime[0] = prime[1] = false;\n        \n        for (int i = 2; i <= n; i++) {\n            if (prime[i]) {\n                int j = i * i;\n                \n                while (j <= n) {\n                    prime[j] = false;\n                    j += i;\n                }\n            }\n        }\n        \n        for (int i = 2; i < n; i++) {\n            if (i + i > n) break;\n            if (prime[i] && prime[n - i]) {\n                ans.push_back({i, n - i});\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```\n# Java Code\n```\nimport java.util.*;\n\nclass Solution {\n    public List<List<Integer>> findPrimePairs(int n) {\n        List<List<Integer>> ans = new ArrayList<>();\n        \n        boolean[] prime = new boolean[n+1];\n        Arrays.fill(prime, true);\n        prime[0] = prime[1] = false;\n        \n        for (int i = 2; i <= n; i++) {\n            if (prime[i]) {\n                int j = i * i;\n                \n                while (j <= n) {\n                    prime[j] = false;\n                    j += i;\n                }\n            }\n        }\n        \n        for (int i = 2; i < n; i++) {\n            if (i + i > n) break;\n            if (prime[i] && prime[n - i]) {\n                ans.add(Arrays.asList(i, n - i));\n            }\n        }\n        \n        return ans;\n    }\n}\n\n```
['Math', 'C++', 'Java', 'Python3']