## Link: https://leetcode.com/problems/prime-pairs-with-target-sum/description/
## 思路
Sieve Algorithm
## Code

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        isPrime = [True]*(n+1)
        isPrime[0], isPrime[1] = False, False
        for i in range(2, int(sqrt(n))+1):
            if isPrime[i]:
                for j in range(2*i, n, i):
                    isPrime[j] = False

        ans = []
        for i in range(2, n):
            if isPrime[i] and isPrime[n-i] and i<=n-i:
                ans.append([i, n-i])
        return ans