Prime Pairs With Target Sum

Medium
1323.

Prime Pairs With Target Sum

Prime Pairs With Target Sum is a medium coding problem on arrays, math and enumeration, asked in Amazon, Google and TCS interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number[][]}
 */
var findPrimePairs = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Precompute which numbers up to n are prime with the sieve of Eratosthenes.

  2. Hint 2

    Then try every x from 2 up to n / 2 and keep it when both x and n - x are prime.

  3. Hint 3

    Scanning x upward produces the pairs already in the required order, and x <= n - x guarantees x <= 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

  1. Build a sieve: mark 0 and 1 as not prime, and for each prime i with i·i <= n, mark i·i, i·i + i, … as composite.
  2. For x = 2, 3, … while x <= n - x, add [x, n - x] if both are prime.
  3. 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 == y is 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