Finding Prime Pairs Summing to a Given Number Using C++ And Sieve
Intuition\nThe problem asks for pairs of prime numbers that sum up to a given number n. This immediately suggests the use of a prime-checking mechanism. A Sieve
# Intuition\nThe problem asks for pairs of prime numbers that sum up to a given number `n`. This immediately suggests the use of a prime-checking mechanism. A Sieve of Eratosthenes can be applied to precompute all primes up to `n`, as it allows efficient checking of whether a number is prime.\n\n# Approach\n1. First, apply the Sieve of Eratosthenes to mark non-prime numbers up to `n`.\n2. Then, iterate through the range from 1 to `n/2`. For each number `i`, check if both `i` and `n - i` are prime.\n3. If both are prime, store the pair as a valid result.\n4. Return the list of prime pairs.\n\n# Complexity\n- **Time complexity**: \n  - The Sieve of Eratosthenes runs in \\(O(n \\log(\\log(n)))\\).\n  - The loop to find valid pairs takes \\(O(n/2)\\), so the total time complexity is approximately \\(O(n \\log(\\log(n)))\\).\n  \n- **Space complexity**: \n  - The sieve array takes \\(O(n)\\) space.\n  - The result vector stores up to \\(O(n)\\) pairs, making the total space complexity \\(O(n)\\).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<int> sieve(n + 1, 0); \n        sieve[0] = sieve[1] = 1; // Mark 0 and 1 as non-prime\n        \n        // Sieve of Eratosthenes to find primes up to n\n        for (int i = 2; i * i <= n; ++i) {\n            if (sieve[i] == 0) {\n                for (int j = 2; i * j <= n; ++j) {\n                    sieve[i * j] = 1; // Mark multiples of i as non-prime\n                }\n            }\n        }\n        \n        vector<vector<int>> primes;\n        // Find prime pairs (i, n - i)\n        for (int i = 1; i <= n / 2; ++i) {\n            if (sieve[i] == 0 && sieve[n - i] == 0) {\n                primes.push_back({i, n - i}); // Both i and n - i are prime\n            }\n        }\n        return primes;\n    }\n};\n```
['C++']