Prime Pairs With Target Sum

Problem

You are given an integer n. We say that two integers x and y form a prime number pair if:

1 <= x <= y <= n
x + y == n
x and y are 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.

Examples

Example 1

1
2
3
4


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

1
2
3


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 <= 10^6

Solution

Method 1 – Sieve of Eratosthenes and Two Pointer Search

Intuition

To find all pairs of primes (x, y) such that x + y = n and 1 <= x <= y <= n, we need to efficiently check for primes up to n. The Sieve of Eratosthenes is ideal for this. For each x from 2 to n//2, if both x and n-x are prime, (x, n-x) is a valid pair.

Approach

Use the Sieve of Eratosthenes to precompute all primes up to n.
For each x in [2, n//2], check if both x and n-x are prime.
If so, add [x, n-x] to the result.
Return the result sorted by x (which is natural by construction).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include <vector>
using namespace std;
vector<vector<int>> findPrimePairs(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i*i; j <= n; j += i) is_prime[j] = false;
        }
    }
    vector<vector<int>> res;
    for (int x = 2; x <= n/2; ++x) {
        int y = n - x;
        if (is_prime[x] && is_prime[y]) res.push_back({x, y});
    }
    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func findPrimePairs(n int) [][]int {
    isPrime := make([]bool, n+1)
    for i := range isPrime {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    res := [][]int{}
    for x := 2; x <= n/2; x++ {
        y := n - x
        if isPrime[x] && isPrime[y] {
            res = append(res, []int{x, y})
        }
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


import java.util.*;
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 i = 2; i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i*i; j <= n; j += i) isPrime[j] = false;
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int x = 2; x <= n/2; ++x) {
            int y = n - x;
            if (isPrime[x] && isPrime[y]) {
                res.add(Arrays.asList(x, y));
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


fun findPrimePairs(n: Int): List<List<Int>> {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false; isPrime[1] = false
    for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..n step i) isPrime[j] = false
        }
    }
    val res = mutableListOf<List<Int>>()
    for (x in 2..n/2) {
        val y = n - x
        if (isPrime[x] && isPrime[y]) res.add(listOf(x, y))
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from typing import List
def findPrimePairs(n: int) -> List[List[int]]:
    is_prime = [True] * (n+1)
    is_prime[0:2] = [False, False]
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    res = []
    for x in range(2, n//2+1):
        y = n - x
        if is_prime[x] and is_prime[y]:
            res.append([x, y])
    return res

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


fn find_prime_pairs(n: i32) -> Vec<Vec<i32>> {
    let n = n as usize;
    let mut is_prime = vec![true; n+1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..=((n as f64).sqrt() as usize) {
        if is_prime[i] {
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i;
            }
        }
    }
    let mut res = vec![];
    for x in 2..=n/2 {
        let y = n - x;
        if is_prime[x] && is_prime[y] {
            res.push(vec![x as i32, y as i32]);
        }
    }
    res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


export function findPrimePairs(n: number): number[][] {
    const isPrime = Array(n+1).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (let j = i*i; j <= n; j += i) isPrime[j] = false;
        }
    }
    const res: number[][] = [];
    for (let x = 2; x <= n/2; ++x) {
        const y = n - x;
        if (isPrime[x] && isPrime[y]) res.push([x, y]);
    }
    return res;
}

Complexity

⏰ Time complexity: O(n log log n) for sieve, and O(n) for checking pairs, so overall O(n log log n).
🧺 Space complexity: O(n) for the sieve array.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Sieve of Eratosthenes and Two Pointer Search#

Intuition#

Approach#

Code#

Complexity#