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 <= 106Problem Overview: Given an integer n, return all pairs of prime numbers [x, y] such that x + y = n and x ≤ y. The task combines prime number generation with efficient pair enumeration.
Approach 1: Trial Division with Reduction (Time: O(n√n), Space: O(1))
Iterate the first value a from 2 to n / 2. For each candidate, compute b = n - a. Check if both numbers are prime using trial division up to √x. If both checks pass, record the pair [a, b]. This approach uses pure math and number theory logic without extra memory, but repeated primality checks make it slower as n grows.
Approach 2: Sieve of Eratosthenes with Pair Search (Time: O(n log log n) + O(n), Space: O(n))
Precompute all primes up to n using the Sieve of Eratosthenes. The sieve builds a boolean array where isPrime[i] indicates whether i is prime. After preprocessing, iterate a from 2 to n / 2 and check if both a and n - a are marked prime. Each lookup is constant time, so the pair search becomes a simple linear scan. This approach leverages efficient prime generation from number theory and straightforward array lookups, making it the most practical solution for larger inputs.
Recommended for interviews: Start by explaining the trial division approach because it shows you understand primality testing and the pair constraint a + b = n. Then optimize with the Sieve of Eratosthenes. Interviewers typically expect the sieve-based solution since it reduces repeated prime checks and achieves near-linear preprocessing time with constant-time lookups.
This approach involves generating all prime numbers using the Sieve of Eratosthenes up to n. Then, iterate through the list of primes and for each prime x, check if (n - x) is also a prime and greater than or equal to x to form a valid pair.
This solution uses the Sieve of Eratosthenes to compute a list of prime numbers up to n. We then iterate over possible x values, checking that both x and y (where y = n - x) are prime, and that x <= y. We print the pair if both are true.
Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n).
Space Complexity: O(n) for the boolean array storing prime status.
This alternative approach uses trial division to check each potential pair [x, y] for primality, leveraging the fact that x + y = n implies y = n - x. By iterating with x up to n/2, we minimize redundant checks.
This C implementation uses trial division to check each x and corresponding y for primality, iterating up to n/2 to find valid pairs quickly but potentially less efficiently than a sieve approach for large n.
Time Complexity: O(n√n) due to trial division checks for primality.
Space Complexity: O(1) as no extra data structures are used for storing primes.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sieve of Eratosthenes with Pair Search | Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n). |
| Trial Division with Reduction | Time Complexity: O(n√n) due to trial division checks for primality. |
| Preprocessing + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trial Division with Reduction | O(n√n) | O(1) | When memory is constrained or when explaining the basic mathematical idea first |
| Sieve of Eratosthenes with Pair Search | O(n log log n) + O(n) | O(n) | Best general solution when n can be large and many prime checks are required |
Prime Pairs With Target Sum | Leetcode 2761 | Contest 352 • Tech Courses • 947 views views
Watch 8 more video solutions →Practice Prime Pairs With Target Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor