java || beats 100% || Sieve of Eratosthenes || simple explanation
---\n\n## Problem: Prime Number Pairs\n\nYou are given an integer n. You need to find all the prime number pairs [x, y] such that x + y = n.\n\nApproach:\n\nTo 
---\n\n## Problem: Prime Number Pairs\n\nYou are given an integer `n`. You need to find all the prime number pairs `[x, y]` such that `x + y = n`.\n\n**Approach:**\n\nTo solve this problem, we can generate prime numbers up to `n` using the Sieve of Eratosthenes algorithm. We initialize a boolean array `isPrime` of size `n+1` and mark all elements as prime initially. Then, starting from `2`, we iterate up to `n/2` and check if both `p` and `n - p` are prime numbers. If they are prime, we add them as a pair `[p, n-p]` to the result list.\n\n**Java Solution:**\n\n```java\nimport java.util.*;\n\nclass Solution {\n    public List<List<Integer>> findPrimePairs(int n) {\n        boolean[] isPrime = sieveOfEratosthenes(n); // Generate prime numbers up to n\n        List<List<Integer>> res = new ArrayList<>();\n\n        for (int p = 2; p <= n / 2; p++) {\n            if (isPrime[p] && isPrime[n - p]) {\n                res.add(List.of(p, n - p));\n            }\n        }\n\n        return res;\n    }\n\n    private boolean[] sieveOfEratosthenes(int n) {\n        boolean[] isPrime = new boolean[n + 1];\n        Arrays.fill(isPrime, true);\n        isPrime[0] = isPrime[1] = false;\n\n        for (int p = 2; p * p <= n; p++) {\n            if (isPrime[p]) {\n                for (int i = p * p; i <= n; i += p) {\n                    isPrime[i] = false;\n                }\n            }\n        }\n\n        return isPrime;\n    }\n}\n```\n\n**Python Solution:**\n\n```python\nclass Solution:\n    def findPrimePairs(self, n: int) -> List[List[int]]:\n        is_prime = self.sieveOfEratosthenes(n)  # Generate prime numbers up to n\n        res = []\n\n        for p in range(2, n // 2 + 1):\n            if is_prime[p] and is_prime[n - p]:\n                res.append([p, n - p])\n\n        return res\n\n    def sieveOfEratosthenes(self, n: int) -> List[bool]:\n        is_prime = [True] * (n + 1)\n        is_prime[0] = is_prime[1] = False\n\n        p = 2\n        while p * p <= n:\n            if is_prime[p]:\n                for i in range(p * p, n + 1, p):\n                    is_prime[i] = False\n            p += 1\n\n        return is_prime\n```\n\n**C++ Solution:**\n\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<bool> isPrime = sieveOfEratosthenes(n); // Generate prime numbers up to n\n        vector<vector<int>> res;\n\n        for (int p = 2; p <= n / 2; p++) {\n            if (isPrime[p] && isPrime[n - p]) {\n                res.push_back({p, n - p});\n            }\n        }\n\n        return res;\n    }\n\n    vector<bool> sieveOfEratosthenes(int n) {\n        vector<bool> isPrime(n + 1, true);\n        isPrime[0] = isPrime[1] = false;\n\n        for (int p =\n\n 2; p * p <= n; p++) {\n            if (isPrime[p]) {\n                for (int i = p * p; i <= n; i += p) {\n                    isPrime[i] = false;\n                }\n            }\n        }\n\n        return isPrime;\n    }\n};\n```\n\n**Complexity Analysis:**\n\nThe time complexity of the solution is O(n log log n) as we use the Sieve of Eratosthenes algorithm to generate prime numbers. The space complexity is O(n) to store the boolean array `isPrime`.\n\n---\n![leetcode.jpeg](https://assets.leetcode.com/users/images/9cad87c7-0187-43ba-b53e-547ed77944a4_1688273254.9208426.jpeg)\n
['C++', 'Java', 'Python3']