Easy C++ || Very Detailed Explanation of Approach and Sieve of Eratosthenes
Intuition\nWe need to find all the prime numbers within the range 2 to n, and then find the pair. But there are 10^5 numbers so brute force way of finding prime
# Intuition\nWe need to find all the prime numbers within the range 2 to n, and then find the pair. But there are 10^5 numbers so brute force way of finding prime numbers will result in TLE so we need to use Sieve of Eratosthenes to find the primes in range 1 to n. \n\n**Sieve of Eratosthenes** : \nThere is a property that a number N can be exactly divisible by X then X must be less than or equal to sqrt(N).\nThe Sieve of Eratosthenes is an algorithm that efficiently finds all prime numbers up to a given limit by iteratively marking the multiples of each prime number as composite, thereby identifying the primes. So overall time complexity difference of brute force way of finding all prime numbers between 1 to N vs Sieve of Eratosthenes approach is:\nBrute Force : `O(N * sqrt(N))`\nSieve of Eratosthenes : `O(N * log(log N))`\n\n# Approach\n1. First we find all the primes numbers from 0 to n using Sieve of Eratosthenes algorithm and store it in a vector "primes". \n2. Primes is a boolean vector of size n + 1 and stores True in primes[i] if i is prime else False. \n3. Since 0 and 1 are not primes we give a initialze primes[0] and primes[1] to false.\n4. After finding all the primes now we traverse through primes vector to find all the pairs from `i = 2 -> n/2`. We assume ibe the first number and j be the second number. If i be any number then requried second number j becomes `j = n - i`\n5. Say `n = 10`, if `i = 3` then second number j becomes `j = 10 - 3 = 7`. Now after getting the values of i and j we check if i and j are prime numbers using the boolean vector primes if both `primes [i] && primes[j]` are true that means both i and j are prime numbers thus we get requried pair and store it in ans vector.\n\n# Complexity\n- Time complexity:\nO(N + (N * log(log N)))\nN * log(log N) -> for finding all the primes\nN -> traversing through all the primes\n\n\n# Code\n```\nclass Solution {\npublic:\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<vector<int>> ans;\n        vector<bool> primes(n + 1, true);\n        primes[0] = false; // initalizing 0 and 1 numbers to False \n        primes[1] = false;\n\n        for (int i = 2; i * i <= n; i++) // Prime numbers checking using Sieve\n        { \n            if (primes[i]) \n            {\n                for (int j = i * i; j <= n; j += i) \n                {\n                    primes[j] = false;\n                }\n            }\n        }\n\n        \n        for (int i = 2; i <= n / 2; i++) // checking for pairs\n        {\n            int j = n - i;\n            if (primes[i] && primes[j]) {\n                ans.push_back({i, j});\n            }\n        }\n\n        return ans;\n    }\n};\n```\n\nPlease Upvote if found helpful
['C++']