Prime Pairs With Target Sum solution and explanation
8 more videos on this problem
Prime Pairs With Target Sum | Leetcode 2761 | Contest 352Tech Courses · 8:41 · 972 views
2761. Prime Pairs With Target Sum (Leetcode Medium)Programming Live with Larry · 5:40 · 543 views
Leetcode 6916 Prime Pairs With Target Sum | Beats 100%Tech Diet · 6:24 · 284 views
Leetcode 6916 || Prime Pairs With Target Sum || Leetcode Weekly Medium || cppKomal Pal · 12:48 · 241 views
2761. Prime Pairs With Target Sum | LeetCode | Prime Numbers | Sieve Of Eratosthenes (SOE)Coding Gist · 9:06 · 192 views
leetcode 2761. Prime Pairs With Target Sum - Eratosthenes' Sieving MethodCode-Yao · 10:57 · 131 views
6916. Prime Pairs With Target Sum | Leetcode Weekly Contest 352 | Solution Code In Comment.Optimization · 0:51 · 110 views
Prime Pairs With Target Sum- 352nd LeetCode Weekly ContestAlgorithmAl · 3:25 · 93 views
Prime Pairs With Target Sum | Leetcode 2761 | Approach + Code with explanation.Pirai's Academy · 17:14 · 54 views
The problem
You are given an integer n. We say that two integers x and y form a prime number pair if:
1 <= x <= y <= nx + y == nxandyare 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.
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, int(n**0.5) + 1):
if is_prime[p]:
for i in range(p * p, n + 1, p):
is_prime[i] = False
return is_prime
def find_prime_pairs(n):
is_prime = sieve_of_eratosthenes(n)
results = []
for x in range(2, n // 2 + 1):
y = n - x
if is_prime[x] and is_prime[y] and x <= y:
results.append([x, y])
return results
n = 10
pairs = find_prime_pairs(n)
print(pairs)import java.util.ArrayList;
import java.util.List;
public class PrimePairs {
public static List<int[]> findPrimePairs(int n) {
boolean[] isPrime = sieveOfEratosthenes(n);
List<int[]> result = new ArrayList<>();
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime[x] && isPrime[y] && x <= y) {
result.add(new int[]{x, y});
}
}
return result;
}
public static boolean[] sieveOfEratosthenes(int n) {
boolean[] isPrime = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
public static void main(String[] args) {
int n = 10;
List<int[]> pairs = findPrimePairs(n);
System.out.print("[");
for (int i = 0; i < pairs.size(); i++) {
if (i > 0) System.out.print(", ");
System.out.print("[" + pairs.get(i)[0] + ", " + pairs.get(i)[1] + "]");
}
System.out.println("]");
}
}#include <iostream>
#include <vector>
#include <utility>
std::vector<bool> sieveOfEratosthenes(int n) {
std::vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
return isPrime;
}
std::vector<std::pair<int, int>> findPrimePairs(int n) {
std::vector<bool> isPrime = sieveOfEratosthenes(n);
std::vector<std::pair<int, int>> result;
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime[x] && isPrime[y] && x <= y) {
result.emplace_back(x, y);
}
}
return result;
}
int main() {
int n = 10;
auto pairs = findPrimePairs(n);
std::cout << "[";
for (size_t i = 0; i < pairs.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << "[" << pairs[i].first << ", " << pairs[i].second << "]";
}
std::cout << "]\n";
return 0;
}function sieveOfEratosthenes(n) {
let isPrime = Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (let i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
function findPrimePairs(n) {
let isPrime = sieveOfEratosthenes(n);
let result = [];
for (let x = 2; x <= n / 2; x++) {
let y = n - x;
if (isPrime[x] && isPrime[y] && x <= y) {
result.push([x, y]);
}
}
return result;
}
let n = 10;
let pairs = findPrimePairs(n);
console.log(JSON.stringify(pairs));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
bool* sieveOfEratosthenes(int n) {
bool* isPrime = (bool*)malloc((n + 1) * sizeof(bool));
memset(isPrime, true, (n + 1) * sizeof(bool));
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
return isPrime;
}
void findPrimePairs(int n) {
bool* isPrime = sieveOfEratosthenes(n);
printf("[");
bool first = true;
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime[x] && isPrime[y] && x <= y) {
if (!first) printf(", ");
printf("[%d, %d]", x, y);
first = false;
}
}
printf("]\n");
free(isPrime);
}
int main() {
int n = 10;
findPrimePairs(n);
return 0;
}using System;
using System.Collections.Generic;
class PrimePairs {
static bool[] SieveOfEratosthenes(int n) {
bool[] isPrime = new bool[n + 1];
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
return isPrime;
}
static List<int[]> FindPrimePairs(int n) {
bool[] isPrime = SieveOfEratosthenes(n);
List<int[]> result = new List<int[]>();
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime[x] && isPrime[y] && x <= y) {
result.Add(new int[]{x, y});
}
}
return result;
}
static void Main(string[] args) {
int n = 10;
var pairs = FindPrimePairs(n);
Console.Write("[");
for (int i = 0; i < pairs.Count; i++) {
if (i > 0) Console.Write(", ");
Console.Write("[" + pairs[i][0] + ", " + pairs[i][1] + "]");
}
Console.WriteLine("]");
}
}We utilize the Sieve of Eratosthenes in Python to efficiently mark prime numbers up to n. We then iterate to find pairs [x, y] where both are prime and x + y = n.
Time Complexity: O(n log log n) for prime sieve, and O(n) for pair checking.
Space Complexity: O(n) for storing the prime status list.
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.
import math
def is_prime(num):
if num <= 1:
return False
if num <= 3:
return True
if num % 2 == 0 or num % 3 == 0:
return False
for i in range(5, int(math.sqrt(num)) + 1, 6):
if num % i == 0 or num % (i + 2) == 0:
return False
return True
def find_prime_pairs(n):
results = []
for x in range(2, n // 2 + 1):
y = n - x
if is_prime(x) and is_prime(y) and x <= y:
results.append([x, y])
return results
n = 10
pairs = find_prime_pairs(n)
print(pairs)import java.util.ArrayList;
import java.util.List;
public class PrimePairs {
public static boolean isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
public static List<int[]> findPrimePairs(int n) {
List<int[]> result = new ArrayList<>();
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime(x) && isPrime(y) && x <= y) {
result.add(new int[]{x, y});
}
}
return result;
}
public static void main(String[] args) {
int n = 10;
List<int[]> pairs = findPrimePairs(n);
System.out.print("[");
for (int i = 0; i < pairs.size(); i++) {
if (i > 0) System.out.print(", ");
System.out.print("[" + pairs.get(i)[0] + ", " + pairs.get(i)[1] + "]");
}
System.out.println("]");
}
}#include <iostream>
#include <cmath>
#include <vector>
#include <utility>
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
std::vector<std::pair<int, int>> findPrimePairs(int n) {
std::vector<std::pair<int, int>> result;
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime(x) && isPrime(y) && x <= y) {
result.emplace_back(x, y);
}
}
return result;
}
int main() {
int n = 10;
auto pairs = findPrimePairs(n);
std::cout << "[";
for (size_t i = 0; i < pairs.size(); ++i) {
if (i > 0) std::cout << ", ";
std::cout << "[" << pairs[i].first << ", " << pairs[i].second << "]";
}
std::cout << "]\n";
return 0;
}function isPrime(num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 === 0 || num % 3 === 0) return false;
for (let i = 5; i * i <= num; i += 6) {
if (num % i === 0 || num % (i + 2) === 0) return false;
}
return true;
}
function findPrimePairs(n) {
let result = [];
for (let x = 2; x <= n / 2; x++) {
let y = n - x;
if (isPrime(x) && isPrime(y) && x <= y) {
result.push([x, y]);
}
}
return result;
}
let n = 10;
let pairs = findPrimePairs(n);
console.log(JSON.stringify(pairs));#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
void findPrimePairs(int n) {
printf("[");
bool first = true;
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (isPrime(x) && isPrime(y) && x <= y) {
if (!first) printf(", ");
printf("[%d, %d]", x, y);
first = false;
}
}
printf("]\n");
}
int main() {
int n = 10;
findPrimePairs(n);
return 0;
}using System;
using System.Collections.Generic;
class PrimePairs {
static bool IsPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0)
return false;
}
return true;
}
static List<int[]> FindPrimePairs(int n) {
List<int[]> result = new List<int[]>();
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (IsPrime(x) && IsPrime(y) && x <= y) {
result.Add(new int[]{x, y});
}
}
return result;
}
static void Main(string[] args) {
int n = 10;
var pairs = FindPrimePairs(n);
Console.Write("[");
for (int i = 0; i < pairs.Count; i++) {
if (i > 0) Console.Write(", ");
Console.Write("[" + pairs[i][0] + ", " + pairs[i][1] + "]");
}
Console.WriteLine("]");
}
}This Python approach employs trial division to verify primality of x and corresponding y values to identify valid prime pairs, iterating up to n/2 as an optimization.
Time Complexity: O(n√n) dominated by prime checks through trial division.
Space Complexity: O(1) as no additional space beyond variable storage is utilized.
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.
function findPrimePairs(n: number): number[][] {
const primes: boolean[] = new Array(n).fill(true);
for (let i = 2; i < n; ++i) {
if (primes[i]) {
for (let j = i + i; j < n; j += i) {
primes[j] = false;
}
}
}
const ans: number[][] = [];
for (let x = 2; x <= n / 2; ++x) {
const y = n - x;
if (primes[x] && primes[y]) {
ans.push([x, y]);
}
}
return ans;
}func findPrimePairs(n int) (ans [][]int) {
primes := make([]bool, n)
for i := range primes {
primes[i] = true
}
for i := 2; i < n; i++ {
if primes[i] {
for j := i + i; j < n; j += i {
primes[j] = false
}
}
}
for x := 2; x <= n/2; x++ {
y := n - x
if primes[x] && primes[y] {
ans = append(ans, []int{x, y})
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sieve of Eratosthenes with Pair Search | Time Complexity: O(n log log n) for prime sieve, and O(n) for pair checking. |
| Trial Division with Reduction | Time Complexity: O(n√n) dominated by prime checks through trial division. |
| Preprocessing + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trial Division with Reduction | O(n√n) | O(1) | When memory is constrained or when explaining the basic mathematical idea first |
| Sieve of Eratosthenes with Pair Search | O(n log log n) + O(n) | O(n) | Best general solution when n can be large and many prime checks are required |
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.