✅ ✅ 100% fast solution | 266ms runtime 🔥 |  Special Odd Optimization | Sieve of Eratosthenes
Intuition\nWe first store all prime numbers till n in a boolean vector\n Describe your first thoughts on how to solve this problem. \n\n# Complexity\n- Time com
# Intuition\nWe first store all prime numbers till n in a boolean vector\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Complexity\n- Time complexity: O(n log(log n))\n\nThe time complexity of the given code is O(n log log n), where n represents the input limit.\n\nLet\'s analyze the code step by step:\n\n1. The line `isPrime.resize(limit + 1, true);` takes O(n) time, as it resizes the `isPrime` vector to accommodate the numbers from 0 to `limit` and initializes all elements to `true`.\n\n2. The lines `isPrime[0] = isPrime[1] = false;` take constant time, as they update the values of the first two elements in the `isPrime` vector.\n\n3. The loop `for (int num = 2; num * num <= limit; ++num)` runs from 2 to the square root of `limit`. The number of iterations for this loop is approximately \u221An, which gives it a time complexity of O(\u221An).\n\n4. Inside the outer loop, there is an inner loop `for (int multiple = num * num; multiple <= limit; multiple += num)` that iterates from `num * num` to `limit` with a step size of `num`. This loop marks all multiples of `num` as non-prime by setting `isPrime[multiple]` to `false`. The number of iterations for this loop can be approximated as `limit / num`, which gives it a time complexity of O(n/num).\n\n5. Combining the time complexity of the outer loop (O(\u221An)) and the inner loop (O(n/num)) gives the overall time complexity of the code.\n\nTo find the total time complexity, we can calculate the sum of the time complexity for each iteration of the outer loop:\n\n\u221An + \u221An/2 + \u221An/3 + ... + \u221An/\u221An\n\nThis sum can be simplified to O(n log log n) using mathematical analysis. Therefore, the overall time complexity of the code is O(n log log n).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# PLEASE UPVOTE if you understood\n\nAs odd numbers can only be split up into (odd + even), there can only be once possible pair that we need to check that is (2, n-2). As 2 is the only even prime number. This reduces complexity way too much.\n\n# Code\n```\nclass Solution {\n    vector<bool> isPrime;\npublic:\n    void setPrime(const int limit) {\n        // resize the vector to fit values\n        isPrime.resize(limit + 1, true);\n        // 0 and 1 are not prime\n        isPrime[0] = isPrime[1] = false;\n\n        // applying Sieve of Eratosthenes\n        for (int num = 2; num * num <= limit; ++num)\n            if (isPrime[num]) \n                for (int multiple = num * num; multiple <= limit; multiple += num) \n                    isPrime[multiple] = false;\n    }\n    vector<vector<int>> findPrimePairs(int n) {\n        if(n <= 3) return {};\n        vector<vector<int>> ans;\n        setPrime(n);\n        \n        // check for n-2 separately, as it will be the only even \'i\'\n        if(isPrime[n-2]) \n            ans.push_back({2, n-2});\n        if(n & 1) return ans;\n        // we check for only odd \'i\'s, starting from 3\n        // as even \'i\'s won\'t be prime, obviously\n        for(int i=3; i<=n/2; i+=2)\n            if(isPrime[i] && isPrime[n-i]) \n                ans.push_back({i, n-i});\n        return ans;\n    }\n};\n```
['Math', 'C++']