2761. Prime Pairs With Target Sum
Description
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
andy
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
Solutions
Solution 1: Preprocessing + Enumeration
First, we pre-process all the prime numbers within the range of $n$, and record them in the array $primes$, where $primes[i]$ is true
if $i$ is a prime number.
Next, we enumerate $x$ in the range of $[2, \frac{n}{2}]$. In this case, $y = n - x$. If both $primes[x]$ and $primes[y]$ are true
, then $(x, y)$ is a pair of prime numbers, which is added to the answer.
After the enumeration is complete, we return the answer.
The time complexity is $O(n \log \log n)$ and the space complexity is $O(n)$, where $n$ is the number given in the problem.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|