Skip to main content
Talentd

Prime Pairs With Target Sum - Solution & Explanation

MediumArrayMathEnumerationNumber Theory16 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given an integer n, return all pairs of prime numbers [x, y] such that x + y = n and x ā‰¤ y. The task combines prime number generation with efficient pair enumeration.

Approach 1: Trial Division with Reduction (Time: O(nāˆšn), Space: O(1))

Iterate the first value a from 2 to n / 2. For each candidate, compute b = n - a. Check if both numbers are prime using trial division up to āˆšx. If both checks pass, record the pair [a, b]. This approach uses pure math and number theory logic without extra memory, but repeated primality checks make it slower as n grows.

Approach 2: Sieve of Eratosthenes with Pair Search (Time: O(n log log n) + O(n), Space: O(n))

Precompute all primes up to n using the Sieve of Eratosthenes. The sieve builds a boolean array where isPrime[i] indicates whether i is prime. After preprocessing, iterate a from 2 to n / 2 and check if both a and n - a are marked prime. Each lookup is constant time, so the pair search becomes a simple linear scan. This approach leverages efficient prime generation from number theory and straightforward array lookups, making it the most practical solution for larger inputs.

Recommended for interviews: Start by explaining the trial division approach because it shows you understand primality testing and the pair constraint a + b = n. Then optimize with the Sieve of Eratosthenes. Interviewers typically expect the sieve-based solution since it reduces repeated prime checks and achieves near-linear preprocessing time with constant-time lookups.

Approach 1: Sieve of Eratosthenes with Pair Search

This approach involves generating all prime numbers using the Sieve of Eratosthenes up to n. Then, iterate through the list of primes and for each prime x, check if (n - x) is also a prime and greater than or equal to x to form a valid pair.

This solution uses the Sieve of Eratosthenes to compute a list of prime numbers up to n. We then iterate over possible x values, checking that both x and y (where y = n - x) are prime, and that x <= y. We print the pair if both are true.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n).
Space Complexity: O(n) for the boolean array storing prime status.

Try this approach in the editor ā†’

Approach 2: Trial Division with Reduction

This alternative approach uses trial division to check each potential pair [x, y] for primality, leveraging the fact that x + y = n implies y = n - x. By iterating with x up to n/2, we minimize redundant checks.

This C implementation uses trial division to check each x and corresponding y for primality, iterating up to n/2 to find valid pairs quickly but potentially less efficiently than a sieve approach for large n.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(nāˆšn) due to trial division checks for primality.
Space Complexity: O(1) as no extra data structures are used for storing primes.

Try this approach in the editor ā†’

Approach 3: 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.

Next, we enumerate x in the range of [2, \frac{n}{2}]. In this case, y = n - x. If both primes[x] and primes[y] are true, then (x, y) is a pair of prime numbers, which is added to the answer.

After the enumeration is complete, we return the answer.

The time complexity is O(n log log n) and the space complexity is O(n), where n is the number given in the problem.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sieve of Eratosthenes with Pair Search

Time Complexity: O(n log log n) due to the sieve and O(n) for pair checking, leading to overall O(n log log n).
Space Complexity: O(n) for the boolean array storing prime status.

Trial Division with Reduction

Time Complexity: O(nāˆšn) due to trial division checks for primality.
Space Complexity: O(1) as no extra data structures are used for storing primes.

Preprocessing + Enumerationā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Trial Division with ReductionO(nāˆšn)O(1)When memory is constrained or when explaining the basic mathematical idea first
Sieve of Eratosthenes with Pair SearchO(n log log n) + O(n)O(n)Best general solution when n can be large and many prime checks are required

Video Solution

Prime Pairs With Target Sum | Leetcode 2761 | Contest 352 ā€¢ Tech Courses ā€¢ 972 views views

Watch 8 more video solutions ā†’

Frequently Asked Questions

Is Prime Pairs With Target Sum easy or hard?
Prime Pairs With Target Sum is typically rated Medium because it combines two concepts: generating primes efficiently and enumerating valid pairs. The logic is straightforward once you recognize that precomputing primes with a sieve avoids repeated primality checks.
Prime Pairs With Target Sum Python/Java solution
Most implementations build a sieve array up to n and then iterate through candidates from 2 to n/2. The logic is identical across Python, Java, C++, C#, and JavaScript: generate primes with the sieve and append pairs where both numbers are marked prime.
How to solve Prime Pairs With Target Sum in O(n)?
After preprocessing primes with the Sieve of Eratosthenes, the pair enumeration itself runs in O(n). Iterate a from 2 to n/2 and check if isPrime[a] and isPrime[n-a] are both true. Each check is constant time, making the search linear after the sieve preprocessing.
What is the best approach for Prime Pairs With Target Sum?
The Sieve of Eratosthenes with pair search is the most efficient approach. First generate all primes up to n in O(n log log n) time, then iterate from 2 to n/2 and check if both a and n-a are prime using constant-time lookups. This avoids repeated primality tests and scales well for large inputs.
Is Prime Pairs With Target Sum asked at Google/Amazon/Meta?
Problems involving prime generation, pair sums, and number theory frequently appear in technical interviews at companies like Amazon, Google, and fintech startups. Variants that combine prime checks with array scanning are common interview exercises.
What data structure is used in Prime Pairs With Target Sum?
The optimal solution uses a boolean array or list to store primality results generated by the Sieve of Eratosthenes. This structure allows constant-time checks when verifying whether a candidate pair of numbers are both prime.
What is the time complexity of Prime Pairs With Target Sum?
Using the optimal sieve approach, generating primes takes O(n log log n) time and scanning for valid pairs takes O(n). The total complexity is dominated by the sieve step. Space complexity is O(n) for storing the prime lookup array.

Ready to solve this problem?

Practice Prime Pairs With Target Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Primes