Skip to main content
Back to problems
#2761
Medium Algorithms

Prime pairs with target sum

Array Math Enumeration Number Theory
37.1% acceptance
Feb 25, 2026
407
34
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.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub 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;
    if n >= 1 { is_prime[1] = false; }
    let mut i = 2;
    while i * i <= n {
      if is_prime[i] {
        let mut j = i * i;
        while j <= n { is_prime[j] = false; j += i; }
      }
      i += 1;
    }
    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
  }
}