Prime Pairs With Target Sum
MedPrompt
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 == nxandyare 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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through all possible values for the first number x from 2 up to n/2. For each x, it calculates the corresponding y = n - x. It then checks if both x and y are prime numbers using a simple trial division method.
Algorithm
- Initialize an empty list
result. - Loop
xfrom 2 ton / 2. - Let
y = n - x. - Define a helper function
isPrime(k)that checks for primality using trial division up tosqrt(k). - If
isPrime(x)andisPrime(y)are both true, add the pair[x, y]toresult. - Return
result.
Walkthrough
The core idea is to check every potential pair (x, y) that sums to n. We can limit the search space for x to [2, n/2] because of the constraint x <= y. If x > n/2, then y = n - x would be less than n/2, which would violate the x <= y condition we are trying to maintain.
For each x in this range, we define a helper function isPrime(num). This function checks for primality using the trial division method: it attempts to divide num by every integer from 2 up to the square root of num. If any division results in a remainder of 0, the number is composite (not prime).
If both isPrime(x) and isPrime(n-x) return true, we have found a valid prime pair. This pair is added to our result list. The final list of pairs is naturally sorted by x because our main loop iterates x in increasing order.
class Solution { private boolean isPrime(int k) { if (k <= 1) { return false; } for (int i = 2; i * i <= k; i++) { if (k % i == 0) { return false; } } return true; } public List<List<Integer>> findPrimePairs(int n) { List<List<Integer>> result = new ArrayList<>(); for (int x = 2; x <= n / 2; x++) { int y = n - x; if (isPrime(x) && isPrime(y)) { result.add(Arrays.asList(x, y)); } } return result; }}Complexity
Time
O(n * sqrt(n)). The main loop runs `n/2` times. Inside the loop, the `isPrime` checks take up to `O(sqrt(x))` and `O(sqrt(n-x))`. In the worst case, this is `O(sqrt(n))`. Thus, the total time is `O(n * sqrt(n))`.
Space
O(1) auxiliary space, excluding the space required for the output list.
Trade-offs
Pros
Simple to understand and implement.
Very low memory usage.
Cons
Extremely inefficient due to repeated primality tests.
Will result in a 'Time Limit Exceeded' error for larger values of
n.
Solutions
Solution
class Solution {public List<List<Integer>> findPrimePairs(int n) { boolean[] primes = new boolean[n]; Arrays.fill(primes, true); for (int i = 2; i < n; ++i) { if (primes[i]) { for (int j = i + i; j < n; j += i) { primes[j] = false; } } } List<List<Integer>> ans = new ArrayList<>(); for (int x = 2; x <= n / 2; ++x) { int y = n - x; if (primes[x] && primes[y]) { ans.add(List.of(x, y)); } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.