#2761

Medium

LeetCode Problem Workspace

Prime Pairs With Target Sum

Find all prime number pairs that sum up to a given integer n using an efficient sieve-based array approach.

Problem Statement

Given an integer n, identify all unique pairs of integers [x, y] such that both x and y are prime numbers and x + y equals n. A prime number is any natural number greater than 1 with exactly two positive divisors, 1 and itself.

Return a 2D list of all prime pairs sorted in ascending order of the first element. If no valid pairs exist, return an empty array. For example, when n = 10, the output should be [[3,7],[5,5]].

Examples

Example 1

Input: n = 10

Output: [[3,7],[5,5]]

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: []

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

Solution Approach

Precompute primes using Sieve of Eratosthenes

Use a boolean array to mark all numbers up to n as prime or not. This allows O(1) prime checks when generating candidate pairs, directly addressing the array plus math pattern.

Iterate through primes to find valid pairs

Loop through all primes less than or equal to n/2 and check if n - prime is also prime. Add [prime, n-prime] to the result. This ensures each pair is unique and sorted by the first element.

Return sorted list

Since we iterate in increasing order, pairs are already sorted by the first element. Return the 2D list of prime pairs, handling edge cases like n < 4 which yields no pairs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log log n) for the sieve and O(n) for iterating primes up to n/2. Space complexity is O(n) for storing the prime flags array.

What Interviewers Usually Probe

Expect efficient prime computation to avoid TLE for n up to 10^6.
Look for correct handling of duplicates and symmetry in prime pairs.
Check if the candidate uses O(1) lookups for prime verification.

Common Pitfalls or Variants

Common pitfalls

Not using a sieve and checking primes naively causing timeouts.
Including duplicate pairs like [7,3] after [3,7].
Failing to handle small n values where no prime pairs exist.

Follow-up variants

Return prime pairs that sum to n with the largest first element instead of sorted order.
Count the number of prime pairs without returning the full list.
Allow n to be odd and find all prime pairs including repeated elements like [5,5].

FAQ

What is the most efficient way to find prime pairs with target sum?

Precompute all primes up to n using a sieve, then iterate primes less than n/2 checking if n minus the prime is also prime.

Does the order of pairs matter in the output?

Yes, pairs should be sorted in increasing order of the first element to match the problem's requirement.

Can n be less than 4 and still have prime pairs?

No, because the smallest sum of two primes is 2+2=4, so any n < 4 returns an empty array.

Are duplicate pairs like [7,3] allowed if [3,7] exists?

No, only unique pairs where the first element is less than or equal to the second are included.

What pattern does this problem follow?

This is an array plus math pattern focusing on prime generation and pair enumeration, ensuring efficient sum checks.

terminal

Solution

Solution 1: Preprocessing + Enumeration

First, we pre-process all the prime numbers within the range of $n$, and record them in the array $primes$, where $primes[i]$ is `true` if $i$ is a prime number.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        primes = [True] * n
        for i in range(2, n):
            if primes[i]:
                for j in range(i + i, n, i):
                    primes[j] = False
        ans = []
        for x in range(2, n // 2 + 1):
            y = n - x
            if primes[x] and primes[y]:
                ans.append([x, y])
        return ans

Continue Practicing

#3044 most frequent prime #3411 maximum subarray with equal products #3574 maximize subarray gcd score