Beats 100% || Easy-to-Understand || Intuition + Approach Explained
Intuition\nSimple function to find prime would give TLE. Hence we need a more optimised solution to pass prime numbers and then perform the given conditions on 
# Intuition\nSimple function to find prime would give TLE. Hence we need a more optimised solution to pass prime numbers and then perform the given conditions on the question. \n\nThe **Sieve of Eratosthenes** is an efficient algorithm for finding all prime numbers up to a given limit n. Here\'s a three-line description of the algorithm:\n\n1. Initialize a boolean array of size n+1 and mark all elements as true.\n2. Starting from the first prime number, iterate through the array and mark all multiples of each prime as false, as they cannot be prime numbers.\n3. The remaining unmarked numbers in the array are prime numbers.\n\n\n# Approach\nWe first generate a boolean array isPrime of size n + 1, where each index represents a number and the value at that index indicates whether it\'s prime or not. We initialize all elements as true initially. Then we use the Sieve of Eratosthenes algorithm to mark non-prime numbers as false. This step has a time complexity of O(n log log n).\n\nAfter generating the primes, we iterate from 2 to n / 2 and check if both i and n - i are prime using the isPrime array. If they are both prime, we add them to the ans vector.\n\nThe line **isPrime[0] = isPrime[1] = false**; is used to explicitly mark the numbers 0 and 1 as non-prime. In most number theory conventions, 0 and 1 are not considered prime numbers. By setting isPrime[0] and isPrime[1] to false, we indicate that these numbers should be treated as non-prime.\n\nIn the Sieve of Eratosthenes algorithm, the loop starts from i = 2, so explicitly marking isPrime[0] and isPrime[1] as false ensures that they are not mistakenly considered as prime numbers during the algorithm execution.\n\n# Complexity\n- Time complexity: ***O(n log log n).***\n\n\n- Space complexity: ***O(n)*** since it requires an additional boolean array of size n+1 to store the prime flags. \n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<bool> isPrime(n + 1, true);\n        isPrime[0] = isPrime[1] = false;\n\n        for (int i = 2; i * i <= n; i++) {\n            if (isPrime[i]) {\n                for (int j = i * i; j <= n; j += i) {\n                    isPrime[j] = false;\n                }\n            }\n        }\n\n        vector<vector<int>> ans;\n        for (int i = 2; i <= n / 2; i++) {\n            if (isPrime[i] && isPrime[n - i]) {\n                ans.push_back({i, n - i});\n            }\n        }\n     return ans;\n    }\n};\n\n\n```
['C++']