💡 C++ | Simple Logic | With Full Explanation ✏️
Approach:\nThe code uses the Sieve of Eratosthenes to identify all prime numbers up to \'n\' efficiently. It then iterates through possible pairs of numbers, ch
# Approach:\nThe code uses the Sieve of Eratosthenes to identify all prime numbers up to \'n\' efficiently. It then iterates through possible pairs of numbers, checking if both the number and its complement (sum to \'n\') are prime, and adds valid pairs to the result list. This approach ensures that the solution is both time-efficient and space-efficient for finding prime pairs that sum up to a given number. \uD83D\uDC40\n\n\n\n\n\n# Complexity\n- Time complexity:\n```O(N\u2217Log(Log(N)))```\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<bool>arr(n+1,true);\n        arr.at(0)=false;\n        arr.at(1)=false;\n        for(int j=2;j*j<n+1;j++){\n            if(arr.at(j)){\n                for(int k=j*j;k<n+1;k+=j){\n                    arr.at(k)=false;\n                }\n            }\n        }\n        vector<vector<int>>ans;\n        for(int k=2;k<=(n+1)/2;k++){\n            if(arr.at(k)&&arr.at(n-k)&&(n-k>=k)){\n                ans.push_back({k,n-k});\n            }\n        }\n        return ans;\n    }\n};\n```\n\n# Step-by-Step Explanation:\n\n**1. Sieve of Eratosthenes Initialization:**\n\n\n```\nvector<bool> arr(n+1, true);\narr.at(0) = false;\narr.at(1) = false;\n```\n- A boolean vector arr of size n+1 is initialized with true values, indicating that all numbers are initially assumed to be prime.\n- The first two elements, arr[0] and arr[1], are set to false because 0 and 1 are not prime numbers.\n\n**2. Sieve of Eratosthenes Algorithm:**\n\n```\nfor (int j = 2; j * j < n + 1; j++) {\n    if (arr.at(j)) {\n        for (int k = j * j; k < n + 1; k += j) {\n            arr.at(k) = false;\n        }\n    }\n}\n\n```\n- The outer loop iterates over each number j from 2 to the square root of n+1.\n- If arr[j] is true, it indicates that j is a prime number.\n- The inner loop marks all multiples of j (starting from j*j) as false, indicating they are not prime.\n- This process eliminates non-prime numbers efficiently.\n\n\n**2. Finding Prime Pairs:**\n\n```\nvector<vector<int>> ans;\nfor (int k = 2; k <= (n + 1) / 2; k++) {\n    if (arr.at(k) && arr.at(n - k) && (n - k >= k)) {\n        ans.push_back({k, n - k});\n    }\n}\n```\n- A vector ans is initialized to store the pairs of prime numbers.\n- The loop iterates over each number k from 2 to (n+1)/2.\n- For each k, it checks if both k and n-k are prime numbers using the boolean array arr.\n- Additionally, it checks if n-k is greater than or equal to k to avoid duplicate pairs and ensure the order.\n- If both conditions are met, the pair {k, n-k} is added to the ans vector.\n\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/3f696237-5498-43a7-97da-6c382b493755_1717388390.637768.jpeg)\n\n\n# Ask any doubt !!!\nMessage me on LinkedIn if you have any doubt related to this question \uD83D\uDE0A\uD83D\uDC47\n\uD83D\uDD17 https://www.linkedin.com/in/bhardwajtushar2004/\n\n# Connect with me on LinkedIn :)
['C++']