Algorithms
Medium
2761
2873
Prime Pairs With Target Sum
prime-pairs-with-target-sum
"""
You are given an integer n. We say that two integers x and y form a prime number pair if:

 * 1 <= x <= y <= n
 * x + y == n
 * x and y are prime numbers

Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.

Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.

Example 1:

Input: n = 10
Output: [[3,7],[5,5]]
Explanation: In this example, there are two prime pairs that satisfy the criteria.
These pairs are [3,7] and [5,5], and we return them in the sorted order as described in the problem statement.

Example 2:

Input: n = 2
Output: []
Explanation: We can show that there is no prime number pair that gives a sum of 2, so we return an empty array.


Constraints:

 * 1 <= n <= 106
"""
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        
You are given an integer n. We say that two integers x and y form a prime number pair if:

 * 1 <= x <= y <= n
 * x + y == n
 * x and y are prime numbers

Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.

Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.

Example 1:

Input: n = 10
Output: [[3,7],[5,5]]
Explanation: In this example, there are two prime pairs that satisfy the criteria.
These pairs are [3,7] and [5,5], and we return them in the sorted order as described in the problem statement.

Example 2:

Input: n = 2
Output: []
Explanation: We can show that there is no prime number pair that gives a sum of 2, so we return an empty array.


Constraints:

 * 1 <= n <= 106


Please complete the code below to solve above prblem:
```python
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        
```

my_solution = Solution()

test_input = { "n": 10 }
assert my_solution.findPrimePairs(**test_input) == [[3,7],[5,5]]

test_input = { "n": 2 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 1 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 3 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 4 }
assert my_solution.findPrimePairs(**test_input) == [[2,2]]

test_input = { "n": 5 }
assert my_solution.findPrimePairs(**test_input) == [[2,3]]

test_input = { "n": 6 }
assert my_solution.findPrimePairs(**test_input) == [[3,3]]

test_input = { "n": 7 }
assert my_solution.findPrimePairs(**test_input) == [[2,5]]

test_input = { "n": 8 }
assert my_solution.findPrimePairs(**test_input) == [[3,5]]

test_input = { "n": 9 }
assert my_solution.findPrimePairs(**test_input) == [[2,7]]

test_input = { "n": 11 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 12 }
assert my_solution.findPrimePairs(**test_input) == [[5,7]]

test_input = { "n": 13 }
assert my_solution.findPrimePairs(**test_input) == [[2,11]]

test_input = { "n": 14 }
assert my_solution.findPrimePairs(**test_input) == [[3,11],[7,7]]

test_input = { "n": 15 }
assert my_solution.findPrimePairs(**test_input) == [[2,13]]

test_input = { "n": 16 }
assert my_solution.findPrimePairs(**test_input) == [[3,13],[5,11]]

test_input = { "n": 17 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 18 }
assert my_solution.findPrimePairs(**test_input) == [[5,13],[7,11]]

test_input = { "n": 19 }
assert my_solution.findPrimePairs(**test_input) == [[2,17]]

test_input = { "n": 20 }
assert my_solution.findPrimePairs(**test_input) == [[3,17],[7,13]]

test_input = { "n": 21 }
assert my_solution.findPrimePairs(**test_input) == [[2,19]]

test_input = { "n": 22 }
assert my_solution.findPrimePairs(**test_input) == [[3,19],[5,17],[11,11]]

test_input = { "n": 23 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 24 }
assert my_solution.findPrimePairs(**test_input) == [[5,19],[7,17],[11,13]]

test_input = { "n": 25 }
assert my_solution.findPrimePairs(**test_input) == [[2,23]]

test_input = { "n": 26 }
assert my_solution.findPrimePairs(**test_input) == [[3,23],[7,19],[13,13]]

test_input = { "n": 27 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 28 }
assert my_solution.findPrimePairs(**test_input) == [[5,23],[11,17]]

test_input = { "n": 29 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 30 }
assert my_solution.findPrimePairs(**test_input) == [[7,23],[11,19],[13,17]]

test_input = { "n": 31 }
assert my_solution.findPrimePairs(**test_input) == [[2,29]]

test_input = { "n": 32 }
assert my_solution.findPrimePairs(**test_input) == [[3,29],[13,19]]

test_input = { "n": 33 }
assert my_solution.findPrimePairs(**test_input) == [[2,31]]

test_input = { "n": 34 }
assert my_solution.findPrimePairs(**test_input) == [[3,31],[5,29],[11,23],[17,17]]

test_input = { "n": 35 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 36 }
assert my_solution.findPrimePairs(**test_input) == [[5,31],[7,29],[13,23],[17,19]]

test_input = { "n": 37 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 38 }
assert my_solution.findPrimePairs(**test_input) == [[7,31],[19,19]]

test_input = { "n": 39 }
assert my_solution.findPrimePairs(**test_input) == [[2,37]]

test_input = { "n": 40 }
assert my_solution.findPrimePairs(**test_input) == [[3,37],[11,29],[17,23]]

test_input = { "n": 41 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 42 }
assert my_solution.findPrimePairs(**test_input) == [[5,37],[11,31],[13,29],[19,23]]

test_input = { "n": 43 }
assert my_solution.findPrimePairs(**test_input) == [[2,41]]

test_input = { "n": 44 }
assert my_solution.findPrimePairs(**test_input) == [[3,41],[7,37],[13,31]]

test_input = { "n": 45 }
assert my_solution.findPrimePairs(**test_input) == [[2,43]]

test_input = { "n": 46 }
assert my_solution.findPrimePairs(**test_input) == [[3,43],[5,41],[17,29],[23,23]]

test_input = { "n": 47 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 48 }
assert my_solution.findPrimePairs(**test_input) == [[5,43],[7,41],[11,37],[17,31],[19,29]]

test_input = { "n": 49 }
assert my_solution.findPrimePairs(**test_input) == [[2,47]]

test_input = { "n": 50 }
assert my_solution.findPrimePairs(**test_input) == [[3,47],[7,43],[13,37],[19,31]]

test_input = { "n": 51 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 52 }
assert my_solution.findPrimePairs(**test_input) == [[5,47],[11,41],[23,29]]

test_input = { "n": 53 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 54 }
assert my_solution.findPrimePairs(**test_input) == [[7,47],[11,43],[13,41],[17,37],[23,31]]

test_input = { "n": 55 }
assert my_solution.findPrimePairs(**test_input) == [[2,53]]

test_input = { "n": 56 }
assert my_solution.findPrimePairs(**test_input) == [[3,53],[13,43],[19,37]]

test_input = { "n": 57 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 58 }
assert my_solution.findPrimePairs(**test_input) == [[5,53],[11,47],[17,41],[29,29]]

test_input = { "n": 59 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 60 }
assert my_solution.findPrimePairs(**test_input) == [[7,53],[13,47],[17,43],[19,41],[23,37],[29,31]]

test_input = { "n": 61 }
assert my_solution.findPrimePairs(**test_input) == [[2,59]]

test_input = { "n": 62 }
assert my_solution.findPrimePairs(**test_input) == [[3,59],[19,43],[31,31]]

test_input = { "n": 63 }
assert my_solution.findPrimePairs(**test_input) == [[2,61]]

test_input = { "n": 64 }
assert my_solution.findPrimePairs(**test_input) == [[3,61],[5,59],[11,53],[17,47],[23,41]]

test_input = { "n": 65 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 66 }
assert my_solution.findPrimePairs(**test_input) == [[5,61],[7,59],[13,53],[19,47],[23,43],[29,37]]

test_input = { "n": 67 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 68 }
assert my_solution.findPrimePairs(**test_input) == [[7,61],[31,37]]

test_input = { "n": 69 }
assert my_solution.findPrimePairs(**test_input) == [[2,67]]

test_input = { "n": 70 }
assert my_solution.findPrimePairs(**test_input) == [[3,67],[11,59],[17,53],[23,47],[29,41]]

test_input = { "n": 71 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 72 }
assert my_solution.findPrimePairs(**test_input) == [[5,67],[11,61],[13,59],[19,53],[29,43],[31,41]]

test_input = { "n": 73 }
assert my_solution.findPrimePairs(**test_input) == [[2,71]]

test_input = { "n": 74 }
assert my_solution.findPrimePairs(**test_input) == [[3,71],[7,67],[13,61],[31,43],[37,37]]

test_input = { "n": 75 }
assert my_solution.findPrimePairs(**test_input) == [[2,73]]

test_input = { "n": 76 }
assert my_solution.findPrimePairs(**test_input) == [[3,73],[5,71],[17,59],[23,53],[29,47]]

test_input = { "n": 77 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 78 }
assert my_solution.findPrimePairs(**test_input) == [[5,73],[7,71],[11,67],[17,61],[19,59],[31,47],[37,41]]

test_input = { "n": 79 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 80 }
assert my_solution.findPrimePairs(**test_input) == [[7,73],[13,67],[19,61],[37,43]]

test_input = { "n": 81 }
assert my_solution.findPrimePairs(**test_input) == [[2,79]]

test_input = { "n": 82 }
assert my_solution.findPrimePairs(**test_input) == [[3,79],[11,71],[23,59],[29,53],[41,41]]

test_input = { "n": 83 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 84 }
assert my_solution.findPrimePairs(**test_input) == [[5,79],[11,73],[13,71],[17,67],[23,61],[31,53],[37,47],[41,43]]

test_input = { "n": 85 }
assert my_solution.findPrimePairs(**test_input) == [[2,83]]

test_input = { "n": 86 }
assert my_solution.findPrimePairs(**test_input) == [[3,83],[7,79],[13,73],[19,67],[43,43]]

test_input = { "n": 87 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 88 }
assert my_solution.findPrimePairs(**test_input) == [[5,83],[17,71],[29,59],[41,47]]

test_input = { "n": 89 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 90 }
assert my_solution.findPrimePairs(**test_input) == [[7,83],[11,79],[17,73],[19,71],[23,67],[29,61],[31,59],[37,53],[43,47]]

test_input = { "n": 91 }
assert my_solution.findPrimePairs(**test_input) == [[2,89]]

test_input = { "n": 92 }
assert my_solution.findPrimePairs(**test_input) == [[3,89],[13,79],[19,73],[31,61]]

test_input = { "n": 93 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 94 }
assert my_solution.findPrimePairs(**test_input) == [[5,89],[11,83],[23,71],[41,53],[47,47]]

test_input = { "n": 95 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 96 }
assert my_solution.findPrimePairs(**test_input) == [[7,89],[13,83],[17,79],[23,73],[29,67],[37,59],[43,53]]

test_input = { "n": 97 }
assert my_solution.findPrimePairs(**test_input) == []

test_input = { "n": 98 }
assert my_solution.findPrimePairs(**test_input) == [[19,79],[31,67],[37,61]]

test_input = { "n": 99 }
assert my_solution.findPrimePairs(**test_input) == [[2,97]]

test_input = { "n": 100 }
assert my_solution.findPrimePairs(**test_input) == [[3,97],[11,89],[17,83],[29,71],[41,59],[47,53]]