2761. Prime Pairs With Target Sum LeetCode Solution

In this guide, you will get 2761. Prime Pairs With Target Sum LeetCode Solution with the best time and space complexity. The solution to Prime Pairs With Target Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Prime Pairs With Target Sum solution in C++
Prime Pairs With Target Sum solution in Java
Prime Pairs With Target Sum solution in Python
Additional Resources

2761. Prime Pairs With Target Sum LeetCode Solution image

Problem Statement of Prime Pairs With Target Sum

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.

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

Complexity Analysis

Time Complexity: O(n\log(\log n))
Space Complexity: O(n)

2761. Prime Pairs With Target Sum LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> findPrimePairs(int n) {
    const vector<bool> isPrime = sieveEratosthenes(n + 1);
    vector<vector<int>> ans;

    for (int i = 2; i <= n / 2; ++i)
      if (isPrime[i] && isPrime[n - i])
        ans.push_back({i, n - i});

    return ans;
  }

 private:
  vector<bool> sieveEratosthenes(int n) {
    vector<bool> isPrime(n, true);
    isPrime[0] = false;
    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;
    return isPrime;
  }
};
/* code provided by PROGIEZ */

2761. Prime Pairs With Target Sum LeetCode Solution in Java

class Solution {
  public List<List<Integer>> findPrimePairs(int n) {
    boolean[] isPrime = sieveEratosthenes(n + 1);
    List<List<Integer>> ans = new ArrayList<>();

    for (int i = 2; i <= n / 2; ++i)
      if (isPrime[i] && isPrime[n - i])
        ans.add(List.of(i, n - i));

    return ans;
  }

  private boolean[] sieveEratosthenes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    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;
    return isPrime;
  }
}
// code provided by PROGIEZ

2761. Prime Pairs With Target Sum LeetCode Solution in Python

class Solution:
  def findPrimePairs(self, n: int) -> list[list[int]]:
    isPrime = self._sieveEratosthenes(n + 1)
    return [[i, n - i] for i in range(2, n // 2 + 1)
            if isPrime[i] and isPrime[n - i]]

  def _sieveEratosthenes(self, n: int) -> list[bool]:
    isPrime = [True] * n
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if isPrime[i]:
        for j in range(i * i, n, i):
          isPrime[j] = False
    return isPrime


j
 # code by PROGIEZ