2761. Prime Pairs With Target Sum

MediumArrayMathEnumerationNumber Theory
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. Initialize an array called primes with n boolean elements set to True. This array will be used to mark whether a number (index) is a prime or not, with True representing prime.

  2. Iterate over the range from 2 to n:

    • For each number i that is still marked as True (prime) in the primes array, iteratively mark its multiples as False (non-prime), starting from i * 2 up to n-1 in increments of i. In doing so, it skips the first multiple, which is the number itself, as that should remain marked as prime.

  3. Once the prime numbers are pre-processed, we create an empty list ans to hold the prime pairs.

  4. Now, we enumerate through values x from 2 up to n // 2 + 1 to find all prime pairs. Why up to n // 2 + 1? Because if x were any larger, y = n - x would be less than x, which means we would be considering the same pair in reverse order, which is not necessary since x <= y.

  5. For each x, we calculate y as n - x. We check if both x and y are marked as True in the primes array.

  6. If both x and y are prime, we append the pair [x, y] to our answer list ans.

  7. Finally, we return the ans list, which now contains all the sorted prime pairs whose elements sum up to n.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's use the integer n = 10 as a small example to illustrate the solution approach.

  1. We initialize an array primes with 11 elements (index 0 to 10), all set to True. The indices represent numbers, and the value at each index represents whether the number is prime (True) or not (False).

  2. Begin the Sieve of Eratosthenes by iterating from 2 to n. For each prime number i that is still marked True, mark its multiples as False. After iterating, the primes array indicates that the prime numbers up to n are 2, 3, 5, 7 because the corresponding indices 2, 3, 5, 7 have remained True.

  3. We create an empty list ans for holding our prime pairs.

  4. Now, we enumerate through the values x from 2 to n // 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 total n.

  5. We start with x = 2 and calculate y = n - x, which gives us y = 10 - 2 = 8. Since 8 is not prime, we move to the next value.

  6. With x = 3, we find y = 10 - 3 = 7. Both 3 and 7 are marked True in the primes array, so we add the pair [3, 7] to our answer list ans.

  7. Proceeding to x = 4, we find y = 10 - 4 = 6. Since 4 is not prime, we do not consider this pair.

  8. Next, with x = 5, we find that y = 10 - 5 = 5. Since both 5 and 5 are prime, we add the pair [5, 5] to ans.

  9. We've now considered all values up to n // 2 + 1, so the enumeration is complete.

  10. 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
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed in two parts:

  1. 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 from i * i up to n, in steps of i. The complexity of the Sieve of Eratosthenes is generally considered to be O(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 from i * i instead of i + i for optimization.

  2. Prime Pair Finding: The second for loop finds pairs of primes that sum up to n. It runs halfway through the prime array (i.e., up to n // 2) as for any prime x greater than n // 2, y = n - x would be less than x and would have been already checked. Therefore, this part has a linear component in its complexity, which is O(n/2), simplifying to O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫