You are given an integer n. We say that two integers x and y form a prime number pair if:
1 <= x <= y <= nx + y == nx and y are prime numbersReturn 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 <= 106The goal of #2761 Prime Pairs With Target Sum is to find all pairs of prime numbers whose sum equals a given integer n. Since repeatedly checking whether numbers are prime is expensive, the key idea is to precompute primes efficiently.
A common approach is to use the Sieve of Eratosthenes to generate all prime numbers up to n. This allows constant-time prime lookups afterward. Once the sieve is built, iterate through possible values x from 2 to n. For each x, compute y = n - x and check if both x and y are prime. To avoid duplicate pairs, only consider cases where x ≤ y.
This transforms the problem into a combination of number theory preprocessing and simple enumeration. The sieve dominates the runtime, giving an efficient solution even for larger values of n. Using a boolean array or set for prime checks keeps lookups fast and memory usage manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sieve of Eratosthenes + Enumeration | O(n log log n) | O(n) |
| Prime Lookup While Scanning Pairs | O(n) | O(n) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Pre-compute all the prime numbers in the range [1, n] using a sieve, and store them in a data structure where they can be accessed in O(1) time.
For x in the range [2, n/2], we can use the pre-computed list of prime numbers to check if both x and n - x are primes. If they are, we add them to the result.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The sieve efficiently precomputes all primes up to n in O(n log log n) time. This avoids repeated primality checks and makes it easy to verify candidate pairs quickly while scanning possible values.
Yes, variations of prime pair or two-number sum problems appear in technical interviews. They test understanding of number theory, preprocessing techniques like the sieve, and efficient enumeration strategies.
A boolean array or hash-based structure for storing prime flags works best. After generating primes using a sieve, this structure allows constant-time checks to verify whether a number is prime during pair enumeration.
The optimal approach uses the Sieve of Eratosthenes to precompute all prime numbers up to n. After building the sieve, iterate through possible values and check whether both x and n − x are prime while ensuring x ≤ y to avoid duplicates.