Sieve Of Eratosthenes - Explaned
First thought - we may think that we can brute force by Iterating $x$ and iterating $y$, then checking if $x + y == n$ and if $x$ and $y$ is prime. \n\n\nfor (i
First thought - we may think that we can brute force by Iterating $x$ and iterating $y$, then checking if $x + y == n$ and if $x$ and $y$ is prime. \n\n```\nfor (int x = 1; x <= n; x++) {\n    for (int y = x; y <= n; y++) {\n        if (x + y == n && isPrime(x) && isPrime(y)) {\n            // now we got [x, y]\n        }\n    }\n}\n```\n\nHowever, $n$ can be up to $10^6$ and O(n ^ 2) solution is a no go. Also checking if a number is a prime number on the fly is expensive. \n\nHence, now we have two things to think about\n\n1. how to optimize the solution without Iterating $x$ and $y$ \n2. how to check if $x$ and $y$ are prime numbers efficiently\n\nTo solve the first problem, by looking at Example 1, we know that we don\'t need to output $[7, 3]$ since it is covered with $[3, 7]$. Also, it is easy to see $y == n - x$ by deriving from $x + y == n$. With these info, we don\'t need to iterate in $O(n^2)$. We just need to check $i$ in $[1 .. n / 2]$. The pair is simply $i$ and $n - i$.\n\n```cpp\nfor (int i = 1; i <= n / 2; i++) {\n    int x = i;\n    int y = n - i;\n    if (isPrime(x) && isPrime(y)) {\n        // we got [x, y]\n    }\n}\n```\n\nTo solve the second problem we can pre-compute all prime numbers up to $n$ by using Sieve of Eatosthenes so that we don\'t need to calculate each time on the fly. \n\n> The Sieve of Eratosthenes is an algorithm used to find all prime numbers up to a given limit. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with 2. The algorithm starts by creating a list of all integers from 2 to the limit. It then marks the first number, 2, as prime and removes all multiples of 2 from the list. The next unmarked number in the list is 3, which is also prime, so it marks it and removes all multiples of 3 from the list. This process continues until all numbers in the list have been marked as prime or composite. The remaining unmarked numbers are the prime numbers up to the given limit.\n\nHere\'s a sample template. \n\n```cpp\nvector<bool> sieveOfEratosthenes(const int n) {\n  assert(n >= 2 && "N must be greater or equal to 2");\n  vector<bool> isPrime(n + 1, true);\n  isPrime[0] = isPrime[1] = false;\n  for (int i = 2; i * i <= n; i++) {\n\tif (isPrime[i]) {\n\t  for (int j = i * i; j <= n; j += i) {\n\t\tisPrime[j] = false;\n\t  }\n\t}\n  }\n  return isPrime;\n}\n```\n\nHere\'s the full solution.\n\n```cpp\nclass Solution {\npublic:\n    vector<bool> sieveOfEratosthenes(const int n) {\n      assert(n >= 2 && "N must be greater or equal to 2");\n      vector<bool> isPrime(n + 1, true);\n      isPrime[0] = isPrime[1] = false;\n      for (int i = 2; i * i <= n; i++) {\n        if (isPrime[i]) {\n          for (int j = i * i; j <= n; j += i) {\n            isPrime[j] = false;\n          }\n        }\n      }\n      return isPrime;\n    }\n\n    vector<vector<int>> findPrimePairs(int n) {\n        vector<vector<int>> ans;\n        if (n == 1) return ans;\n        vector<bool> p = sieveOfEratosthenes(n);\n        for (int i = 1; i <= n / 2; i++) {\n            if (p[i] && p[n - i]) {\n                ans.push_back({i, n - i});\n            }\n        }\n        return ans;\n    }\n};\n```\n\n**p.s. Join us on the LeetCode The Hard Way Discord Study Group for timely discussion! Link in bio.**
['Math', 'Two Pointers', 'C++']