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.
This highly efficient approach avoids the costly repeated primality tests of the brute-force method. It pre-computes all prime numbers up to n using the Sieve of Eratosthenes. This allows for constant-time primality checks. After the pre-computation, it iterates through possible values for x and quickly finds the corresponding pairs.
Algorithm
- Create a boolean array
isPrimeof sizen + 1and initialize all entries totrue. - Mark
isPrime[0]andisPrime[1]asfalse. - Use the Sieve of Eratosthenes algorithm to mark all non-prime numbers up to
nasfalsein theisPrimearray. - Initialize an empty list
result. - Loop
xfrom 2 ton / 2. - If
isPrime[x]andisPrime[n - x]are bothtrue, add the pair[x, n-x]to theresultlist. - Return the
resultlist.
Walkthrough
The core optimization is to solve the subproblem of primality testing efficiently for all numbers up to n at once.
-
Sieve of Eratosthenes: We create a boolean array,
isPrime, of sizen+1. We initialize all entries from 2 tonastrue. We then iterate fromp = 2up tosqrt(n). Ifpis still marked as prime, we iterate through its multiples (starting fromp*p) and mark them as not prime. This process efficiently eliminates all composite numbers, leaving only primes marked astrue. -
Finding Pairs: With the
isPrimearray populated, we can check if any number is prime inO(1)time. We then perform a single pass, iteratingxfrom 2 up ton/2. For eachx, we check if bothxand its complementy = n - xare prime by looking upisPrime[x]andisPrime[y]. -
Collecting Results: If both
xandyare prime, we add the pair[x, y]to our result list. Since we iteratexin increasing order, the resulting list of pairs will be sorted as required.
This combination of an efficient pre-computation step followed by a simple linear scan provides an optimal solution for the given constraints.
class Solution { public List<List<Integer>> findPrimePairs(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p <= n; p++) { if (isPrime[p]) { for (int i = p * p; i <= n; i += p) { isPrime[i] = false; } } } List<List<Integer>> result = new ArrayList<>(); for (int x = 2; x <= n / 2; x++) { if (isPrime[x]) { int y = n - x; if (isPrime[y]) { result.add(Arrays.asList(x, y)); } } } return result; }}Complexity
Time
O(n * log(log(n))). The Sieve of Eratosthenes takes `O(n * log(log(n)))` time. The subsequent linear scan to find pairs takes `O(n)` time. The sieve is the dominant part.
Space
O(n) to store the `isPrime` boolean array.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
A standard and powerful technique for problems involving primes within a fixed range.
Cons
Requires
O(n)auxiliary space, which could be an issue for extremely largen(but is fine forn <= 10^6).
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; }}class Solution {public: vector<vector<int>> findPrimePairs(int n) { bool primes[n]; memset(primes, true, sizeof(primes)); for (int i = 2; i < n; ++i) { if (primes[i]) { for (int j = i + i; j < n; j += i) { primes[j] = false; } } } vector<vector<int>> ans; for (int x = 2; x <= n / 2; ++x) { int y = n - x; if (primes[x] && primes[y]) { ans.push_back({x, y}); } } return ans; }};class Solution: def findPrimePairs(self, n: int) -> List[List[int]]: primes = [True] * n for i in range(2, n): if primes[i]: for j in range(i + i, n, i): primes[j] = False ans = [] for x in range(2, n // 2 + 1): y = n - x if primes[x] and primes[y]: ans . append([x, y]) return ansVideo 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.