Beats 99.27%||Math Explain||C++||variant Sieve of Eratosthenes algorithm finding odd primes
Intuition\n Describe your first thoughts on how to solve this problem. \nThe code uses the Sieve of Eratosthenes algorithm to find and store a list of odd prime
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code uses the Sieve of Eratosthenes algorithm to find and store a list of odd prime numbers up to a given number n. The sieve function is responsible for generating this list. It marks multiples of primes as non-prime in the oddPrime vector. When oddPrime[i]=true, the odd number 2i+1 is a prime!\n[https://youtu.be/7GGhURLPnIs](https://youtu.be/7GGhURLPnIs)\n\nIt is crucial to take n_2sqrt=int(sqrt(n)/2); it saves much time.\n\n[Please the English subtitles if necceassray]\n[https://youtu.be/GxoMWxXLKMc](https://youtu.be/GxoMWxXLKMc)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe function findPrimePairs first checks some base cases and returns appropriate results for n less than or equal to 3 or equal to 4. For other values of n, it calls the sieve function to generate the list of odd primes.\n\nIf n is odd, it checks if n - 2 is an odd prime number. If it is, the function returns a vector containing the pair {2, n - 2}. Otherwise, it returns an empty vector.\n\nIf n is even, the function iterates through odd numbers from 3 to n / 2 and checks if both i  and (n - i)  are prime numbers. If they are, it adds the pair {i, n - i} to the ans vector.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n log log n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution {\npublic:\n    vector<bool> oddPrime;\n\n    void sieve(int n)\n    {\n        int n_2=n>>1;\n        oddPrime.assign(n_2, 1);\n        oddPrime[0]=0;\n        int n_2sqrt=int(sqrt(n)/2);\n        for(int i=1; i<=n_2sqrt; i++){\n            if (oddPrime[i]){\n                int p=2*i+1;\n                for(int j=p*p/2 ; j<n_2; j+=p)\n                    oddPrime[j]=0;\n            }\n        }\n    }\n    vector<vector<int>> findPrimePairs(int n) {\n        if (n<=3) return {};\n        if (n==4) return {{2, 2}};\n        sieve(n);\n        if (n%2==1){\n            if (oddPrime[(n-2)/2]){\n                return {{2, n-2}};\n            }\n            else return {};\n        }\n        vector<vector<int>> ans;\n        for (int i=3; i<=n/2; i+=2){\n            if (oddPrime[i/2] && oddPrime[(n-i)/2])\n                ans.push_back({i, n-i});\n        }\n        return ans;\n    }\n};\n```\n# Code with Explanation in Comments\n```\nclass Solution {\npublic:\n    vector<bool> oddPrime;\n\n    void sieve(int n)\n    {\n        // Dividing n by 2\n        int n_2 = n >> 1;\n        \n        // Assigning n_2 elements with value true (1)\n        oddPrime.assign(n_2, 1);\n        \n        // Marking the first element as false (0)\n        oddPrime[0] = 0;\n        \n        // Calculating the square root of n divided by 2\n        int n_2sqrt = int(sqrt(n) / 2);\n        \n        // Sieve of Eratosthenes algorithm\n        for (int i = 1; i <= n_2sqrt; i++) {\n            if (oddPrime[i]) {\n                // Current prime number\n                int p = 2 * i + 1;\n                \n                // Marking multiples of p as false (0)\n                for (int j = p * p / 2; j < n_2; j += p)\n                    oddPrime[j] = 0;\n            }\n        }\n    }\n    \n    vector<vector<int>> findPrimePairs(int n) {\n        // If n is less than or equal to 3, return an empty vector\n        if (n <= 3)\n            return {};\n        \n        // If n is 4, return a vector containing the pair {2, 2}\n        if (n == 4)\n            return {{2, 2}};\n        \n        // Use the sieve method to generate a list of odd primes\n        sieve(n);\n        \n        // If n is odd\n        if (n % 2 == 1) {\n            if (oddPrime[(n - 2) / 2]) {\n                // If (n-2)/2 is a prime, return a vector containing the pair {2, n-2}\n                return {{2, n - 2}};\n            } else {\n                // Otherwise, return an empty vector\n                return {};\n            }\n        }\n        \n        // n is even\n        vector<vector<int>> ans;\n        \n        // Iterate through odd numbers from 3 to n/2\n        for (int i = 3; i <= n / 2; i += 2) {\n            // Check if both i/2 and (n-i)/2 are primes\n            if (oddPrime[i / 2] && oddPrime[(n - i) / 2])\n                ans.push_back({i, n - i});\n        }\n        \n        // Return the vector containing the prime pairs\n        return ans;\n    }\n};\n\n```
['Math', 'Number Theory', 'C++']