Python find all primes and then two sum
Intuition\nFind all primes with sieve and then two sum\n\n# Complexity\n- Time complexity: $O(n \log \log n)$\n\n- Space complexity: $n / \log n$\n\n# Code\n\nc
# Intuition\nFind all primes with sieve and then two sum\n\n# Complexity\n- Time complexity: $O(n \\log \\log n)$\n\n- Space complexity: $n / \\log n$\n\n# Code\n```\nclass Solution:\n\n  def eratosthenes_sieve(self, n):\n    prime, result, sqrt_n = [True] * n, [2], (int(n ** .5) + 1) | 1\n    for p in range(3, sqrt_n, 2):\n      if prime[p]:\n        result.append(p)\n        prime[p * p::p << 1] = [False] * ((n - p * p - 1) // (p << 1) + 1)\n\n    return result + [p for p in range(sqrt_n, n, 2) if prime[p]]\n\n  def findPrimePairs(self, n: int) -> List[List[int]]:\n    primes_list = self.eratosthenes_sieve(n + 1)\n    primes_set = set(primes_list)\n    res = []\n    for p in primes_list:\n      if p > n - p:\n        break\n      if n - p in primes_set:\n        res.append([p, n - p])\n    return res\n```
['Python3']