2761. Prime Pairs With Target Sum
Problem Description
This problem asks for pairs of prime numbers that sum up to a given integer n
. A prime number pair consists of two prime numbers x
and y
where 1 <= x <= y <= n
, and their sum equals n
. We need to return a 2D list sorted in ascending order by the first element of each pair (x), containing all such pairs or an empty array if no such pairs exist.
A prime number is defined as a number greater than 1
that has no positive divisors other than 1
and itself.
Intuition
The task at hand can be solved by first finding all the prime numbers up to n
and then checking which of these can form pairs that sum to n
.
To identify prime numbers efficiently, we can use the Sieve of Eratosthenes algorithm, which marks all non-prime numbers up to a maximum number (n
in this case) by marking multiples of each prime number starting from 2.
After identifying all prime numbers, we only need to check for pairs where x
is less than or equal to n/2
. This is because if x were greater than n/2
, then y
would have to be less than n/2
to sum up to n
. But since we start checking from the smallest prime (2), once we reach numbers larger than n/2
, weād have already considered all possible pairs with smaller numbers, hence completing the search space for prime pairs where x
and y
can equal n
.
For each potential prime x
up to n/2
, the complement y
is determined by n - x
. If both x
and y
are primes, we record the pair. The algorithm ensures all pairs found are unique since for each x
, there is only one unique y
that meets the criteria.
The pre-computed list of primes is used to quickly check if x
and y
are prime by referencing their values in the array with prime statuses. This results in an efficient and direct solution to the problem.
Learn more about Math patterns.
Solution Approach
The given solution employs the Sieve of Eratosthenes algorithm to pre-process all prime numbers within the range of n
. Let's explore the steps involved:
-
Initialize an array called
primes
withn
boolean elements set toTrue
. This array will be used to mark whether a number (index) is a prime or not, withTrue
representing prime. -
Iterate over the range from 2 to
n
:- For each number
i
that is still marked asTrue
(prime) in theprimes
array, iteratively mark its multiples asFalse
(non-prime), starting fromi * 2
up ton-1
in increments ofi
. In doing so, it skips the first multiple, which is the number itself, as that should remain marked as prime.
- For each number
-
Once the prime numbers are pre-processed, we create an empty list
ans
to hold the prime pairs. -
Now, we enumerate through values
x
from 2 up ton // 2 + 1
to find all prime pairs. Why up ton // 2 + 1
? Because ifx
were any larger,y = n - x
would be less thanx
, which means we would be considering the same pair in reverse order, which is not necessary sincex <= y
. -
For each
x
, we calculatey
asn - x
. We check if bothx
andy
are marked asTrue
in theprimes
array. -
If both
x
andy
are prime, we append the pair[x, y]
to our answer listans
. -
Finally, we return the
ans
list, which now contains all the sorted prime pairs whose elements sum up ton
.
By using the Sieve of Eratosthenes to pre-calculate the prime numbers and then enumerating possible pairs with a range boundary of n // 2 + 1
, the algorithm effectively reduces the problem size and avoids unnecessary comparisons.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the integer n = 10
as a small example to illustrate the solution approach.
-
We initialize an array
primes
with 11 elements (index 0 to 10), all set toTrue
. The indices represent numbers, and the value at each index represents whether the number is prime (True
) or not (False
). -
Begin the Sieve of Eratosthenes by iterating from 2 to
n
. For each prime numberi
that is still markedTrue
, mark its multiples asFalse
. After iterating, theprimes
array indicates that the prime numbers up ton
are2, 3, 5, 7
because the corresponding indices2, 3, 5, 7
have remainedTrue
. -
We create an empty list
ans
for holding our prime pairs. -
Now, we enumerate through the values
x
from 2 ton // 2 + 1
which gives us the range[2, 5]
. We are looking for primes within this range that can pair with another prime number to totaln
. -
We start with
x = 2
and calculatey = n - x
, which gives usy = 10 - 2 = 8
. Since 8 is not prime, we move to the next value. -
With
x = 3
, we findy = 10 - 3 = 7
. Both 3 and 7 are markedTrue
in theprimes
array, so we add the pair[3, 7]
to our answer listans
. -
Proceeding to
x = 4
, we findy = 10 - 4 = 6
. Since 4 is not prime, we do not consider this pair. -
Next, with
x = 5
, we find thaty = 10 - 5 = 5
. Since both 5 and 5 are prime, we add the pair[5, 5]
toans
. -
We've now considered all values up to
n // 2 + 1
, so the enumeration is complete. -
The final answer list
ans
contains the sorted pairs:[[3, 7], [5, 5]]
.
Thus, for n = 10
, the pairs of prime numbers that sum up to n
are [3, 7]
and [5, 5]
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def find_prime_pairs(self, n: int) -> List[List[int]]:
5 # Initialize a list to mark all numbers as prime initially
6 is_prime = [True] * n
7
8 # Sieve of Eratosthenes algorithm to find primes less than n
9 for i in range(2, int(n ** 0.5) + 1): # Loop only up to the square root of n
10 if is_prime[i]:
11 # Mark all multiples of i as non-prime
12 for j in range(i * i, n, i):
13 is_prime[j] = False
14
15 # Initialize a list to store pairs of prime numbers
16 prime_pairs = []
17
18 # Find pairs of primes where both numbers add up to n
19 for x in range(2, n // 2 + 1): # Only need to check up to n // 2
20 y = n - x
21 if is_prime[x] and is_prime[y]:
22 # If both x and y are prime, add them as a pair
23 prime_pairs.append([x, y])
24
25 # Return the list of prime pairs
26 return prime_pairs
27
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6 public List<List<Integer>> findPrimePairs(int n) {
7 // Initialize an array to determine the primality of each number up to n.
8 boolean[] isPrime = new boolean[n];
9 // Assume all numbers are prime initially, set all entries to true.
10 Arrays.fill(isPrime, true);
11
12 // Use the Sieve of Eratosthenes to find all prime numbers less than n.
13 for (int i = 2; i < n; ++i) {
14 if (isPrime[i]) {
15 // If i is prime, then mark all of its multiples as not prime.
16 for (int j = i + i; j < n; j += i) {
17 isPrime[j] = false;
18 }
19 }
20 }
21
22 // List to hold the prime pairs that sum up to n.
23 List<List<Integer>> primePairs = new ArrayList<>();
24
25 // Iterate over possible prime pairs where both numbers are less than n.
26 for (int x = 2; x <= n / 2; ++x) {
27 int y = n - x; // Calculate the complement of x that sums to n.
28 // Check if both numbers are prime.
29 if (isPrime[x] && isPrime[y]) {
30 // Add the pair to the list of prime pairs.
31 primePairs.add(Arrays.asList(x, y));
32 }
33 }
34
35 // Return the list of prime pairs.
36 return primePairs;
37 }
38}
39
1#include <vector>
2#include <cmath>
3#include <cstring>
4
5class Solution {
6public:
7 // Function that returns all unique pairs of prime numbers that add up to 'n'.
8 std::vector<std::vector<int>> findPrimePairs(int n) {
9 // Create a boolean array 'is_prime' initialized to true for prime checking.
10 std::vector<bool> is_prime(n, true);
11
12 // Implement the Sieve of Eratosthenes algorithm to find prime numbers up to 'n'.
13 for (int i = 2; i * i < n; ++i) { // Only go up to the square root of 'n'.
14 if (is_prime[i]) { // If the number is still marked prime:
15 // All multiples of i starting from i*i are marked as not prime.
16 for (int j = i * i; j < n; j += i) {
17 is_prime[j] = false;
18 }
19 }
20 }
21
22 // Vector to store the prime pairs.
23 std::vector<std::vector<int>> prime_pairs;
24
25 // Iterate over the range from 2 to n/2 to find prime pairs.
26 for (int x = 2; x <= n / 2; ++x) {
27 int y = n - x; // The potential prime pair for x that adds up to n.
28 // If both x and y are prime, add them as a pair to the answer list.
29 if (is_prime[x] && is_prime[y]) {
30 prime_pairs.push_back({x, y});
31 }
32 }
33
34 // Return the list of prime pairs.
35 return prime_pairs;
36 }
37};
38
1/**
2 * Checks and returns all prime pairs that sum up to a given number.
3 * @param n The sum target and the upper limit for the prime search.
4 * @returns A two-dimensional array containing all the prime pairs.
5 */
6function findPrimePairs(n: number): number[][] {
7 // Initialize a boolean array to track prime numbers up to n.
8 const isPrime: boolean[] = new Array(n).fill(true);
9
10 // Implement the Sieve of Eratosthenes algorithm to identify primes.
11 for (let index = 2; index < n; ++index) {
12 if (isPrime[index]) {
13 // Mark all multiples of index as not prime.
14 for (let multiple = index * 2; multiple < n; multiple += index) {
15 isPrime[multiple] = false;
16 }
17 }
18 }
19
20 // Array to store pairs of prime numbers whose sum equals n.
21 const primePairs: number[][] = [];
22
23 // Loop through the list of potential prime numbers to find valid pairs.
24 for (let primeCandidate = 2; primeCandidate <= n / 2; ++primeCandidate) {
25 const pairedPrime = n - primeCandidate;
26 // Check if both numbers in the potential pair are prime.
27 if (isPrime[primeCandidate] && isPrime[pairedPrime]) {
28 // Add the prime pair to the results array.
29 primePairs.push([primeCandidate, pairedPrime]);
30 }
31 }
32
33 // Return the array of prime pairs.
34 return primePairs;
35}
36
Time and Space Complexity
Time Complexity
The time complexity of the code can be analyzed in two parts:
-
Sieve Creation: The first
for
loop runs to mark non-prime numbers, which is an implementation of the Sieve of Eratosthenes algorithm. The inner loop marks off multiples of each prime found, starting fromi * i
up ton
, in steps ofi
. The complexity of the Sieve of Eratosthenes is generally considered to beO(n \log \log n)
as it involves multiple passes over the data within certain constraints, not purely linear passes. However, there's a minor modification needed in the given implementation because the inner loop should ideally start fromi * i
instead ofi + i
for optimization. -
Prime Pair Finding: The second
for
loop finds pairs of primes that sum up ton
. It runs halfway through the prime array (i.e., up ton // 2
) as for any primex
greater thann // 2
,y = n - x
would be less thanx
and would have been already checked. Therefore, this part has a linear component in its complexity, which isO(n/2)
, simplifying toO(n)
.
Overall, when combining the O(n \log \log n)
complexity of the Sieve with the O(n)
linear scan for pairs, the dominating factor is O(n \log \log n)
, as this grows faster than O(n)
for larger n
.
Space Complexity
The space complexity is defined by the additional space used for storing the prime number flags. This is a Boolean array of size n
, resulting in O(n)
space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!