Prime Pairs With Target Sum — Solution in Python, Java & C++
Prime Pairs With Target Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Prime Pairs With Target Sum is a medium coding problem on arrays, math and enumeration, asked in Amazon, Google and TCS interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Enumeration, Number Theory
- Asked at: Amazon, Google, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, find every pair of primes [x, y] with x <= y and x + y == n.
Return the pairs as a 2D array sorted by x in increasing order. Return an empty array if there are none.
Example 1
Input: n = 16
Output: [[3,13],[5,11]]
Example 2
Input: n = 11
Output: []
Explanation: An odd sum of two primes needs the prime 2, and 11 - 2 = 9 is not prime.
Example 3
Input: n = 4
Output: [[2,2]]
Constraints
1 <= n <= 10^6
Hints for Prime Pairs With Target Sum
Hint 1
Precompute which numbers up to
nare prime with the sieve of Eratosthenes.Hint 2
Then try every
xfrom 2 up ton / 2and keep it when bothxandn - xare prime.Hint 3
Scanning
xupward produces the pairs already in the required order, andx <= n - xguaranteesx <= y.
How to solve Prime Pairs With Target Sum
Sieve the primes up to n once, then each candidate pair is a constant-time lookup.
Approach
- Build a sieve: mark 0 and 1 as not prime, and for each prime
iwithi·i <= n, marki·i, i·i + i, …as composite. - For
x = 2, 3, …whilex <= n - x, add[x, n - x]if both are prime. - Return the collected pairs.
Why it works
The sieve marks exactly the composites: every composite m <= n has a prime factor p <= √m, and is crossed out from p² onward. Requiring x <= n - x lists each unordered pair once with the smaller value first, and scanning x upward emits the pairs in increasing x.
Complexity
- Time —
O(n log log n) - Space —
O(n)
Pitfalls
x == yis allowed: n = 4 gives[2, 2], and n = 10 includes[5, 5].- For n < 4 there are no pairs at all; make sure the sieve and loop handle tiny n.
- Testing each candidate by trial division costs O(n√n) — fine for small n, slow near 10^6.
Reference solution
Python
from typing import List
def findPrimePairs(n: int) -> List[List[int]]:
if n < 4:
return []
is_p = bytearray([1]) * (n + 1)
is_p[0] = 0
is_p[1] = 0
i = 2
while i * i <= n:
if is_p[i]:
is_p[i * i::i] = bytearray(len(range(i * i, n + 1, i)))
i += 1
return [[x, n - x] for x in range(2, n // 2 + 1) if is_p[x] and is_p[n - x]]Java
public static int[][] findPrimePairs(int n) {
List<int[]> res = new ArrayList<>();
if (n < 4) return new int[0][];
boolean[] comp = new boolean[n + 1];
comp[0] = true;
comp[1] = true;
for (int i = 2; (long) i * i <= n; i++) {
if (!comp[i]) for (int j = i * i; j <= n; j += i) comp[j] = true;
}
for (int x = 2; x <= n - x; x++) if (!comp[x] && !comp[n - x]) res.add(new int[] { x, n - x });
return res.toArray(new int[0][]);
}C++
vector<vector<int>> findPrimePairs(int n) {
vector<vector<int>> res;
if (n < 4) return res;
vector<bool> comp(n + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= n; i++) {
if (!comp[i]) for (long long j = i * i; j <= n; j += i) comp[j] = true;
}
for (int x = 2; x <= n - x; x++) if (!comp[x] && !comp[n - x]) res.push_back({ x, n - x });
return res;
}JavaScript
var findPrimePairs = function(n) {
var res = [];
if (n < 4) return res;
var comp = new Uint8Array(n + 1);
comp[0] = 1;
comp[1] = 1;
for (var i = 2; i * i <= n; i++) {
if (!comp[i]) for (var j = i * i; j <= n; j += i) comp[j] = 1;
}
for (var x = 2; x <= n - x; x++) if (!comp[x] && !comp[n - x]) res.push([x, n - x]);
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays