Prime Pairs With Target Sum

Problem Description

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 [x_i, y_i]. The list should be sorted in increasing order of x_i. If there are no prime number pairs at all, return an empty array.

Key Insights

• A prime number is a natural number greater than 1 with only two factors, itself and 1.
• To find pairs (x, y), we need to check combinations of prime numbers that sum up to n.
• Efficiently finding prime numbers can be done using the Sieve of Eratosthenes.
• We should only consider pairs (x, y) where x ≤ y to avoid duplicates.

Space and Time Complexity

Time Complexity: O(n log log n) for generating primes using the Sieve of Eratosthenes, plus O(n) for finding pairs, resulting in O(n log log n) overall.

Space Complexity: O(n) for storing the list of prime numbers.

Solution

To solve the problem, we will:

1. Use the Sieve of Eratosthenes to generate a list of all primes up to n.
2. Iterate over the list of primes and for each prime x, check if (n - x) is also prime.
3. Collect pairs (x, y) where both x and y are prime and x <= y.

Code Solutions