Sieve of Erathosthenes
Intuition\nIf we can quickly check whether a number up to n is prime, we can solve this problem.\n\nThere are many ways to check if a number is prime, but two o
# Intuition\nIf we can quickly check whether a number up to `n` is prime, we can solve this problem.\n\nThere are many ways to check if a number is prime, but two of the important prime checking algorithms are\n1. Finding the factors of `n` in $$O(1)$$ preprocessing and $$O(\\sqrt n)$$ query time.\n2. Using a Sieve of Erathosthenes in $$O(n\\lg\\lg n)$$ preprocessing and $$O(1)$$ query time.\n\nWe need to check if `n` numbers are prime if we loop through all values of `x`, so we will be making `n` prime-checking queries. As such, approach (1) will take $$O(n\\sqrt n)$$ total time; using a sieve seems like a better approach.\n\n# Approach\nUse a Sieve of Erathosthenes to get which numbers are prime or not prime up to `n`. Test all values of `x` from `2` to `n // 2 - 1` (dividing by `2` so that `x <= y = n - x`).\n\n# Complexity\n- Time complexity: $$O(n\\lg\\lg n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution:\n    def findPrimePairs(self, n: int) -> List[List[int]]:\n        # sieve\n        prime = [False, False] + [True] * (n - 1)\n        for i in range(2, n + 1):\n            if prime[i]:\n                for j in range(i * i, n + 1, i):\n                    prime[j] = False\n        \n        return [[i, n - i] for i in range(2, n // 2 + 1) if prime[i] and prime[n - i]]\n```
['Number Theory', 'Python3']