Sieve of Eratosthenes, Two-Pointer O(nlogn) Python
Intuition\n Describe your first thoughts on how to solve this problem. \nUse sieve of eratosthenes to find all prime numbers <= n\nUse two pointer method to che
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse sieve of eratosthenes to find all prime numbers <= n\nUse two pointer method to check where sum is == n\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findPrimePairs(self, n: int) -> List[List[int]]:\n        def sieve(n):\n            prime = [True for i in range(n+1)]\n            p = 2\n            arr=[]\n            while (p * p <= n):\n                if (prime[p] == True):\n                    for i in range(p * p, n+1, p):\n                        prime[i] = False\n                p += 1\n            for p in range(2, n+1):\n                if prime[p]:\n                    arr.append(p)\n            return arr\n        arr=sieve(n)\n        m=len(arr)\n        ans=[]\n        j=m-1\n        i=0\n        while j>=i:\n            if arr[i]+arr[j]==n:\n                ans.append([arr[i],arr[j]])\n                i+=1\n                j-=1\n            elif arr[i]+arr[j]<n:\n                i+=1\n            else:\n                j-=1\n        return ans\n```
['Math', 'Two Pointers', 'Python', 'Python3']