Leetcode 2761: Prime Pairs With Target Sum

Input: The input consists of a single integer 'n'.

Example: n = 12

Constraints:

• 1 <= n <= 10^6

Output: Return a 2D list of prime pairs [x, y], sorted by x. If no pairs exist, return an empty list.

Example: For n = 12, the output is [[5, 7]].

Constraints:

• The pairs must be sorted in increasing order of x.

Goal: Find all prime pairs such that their sum is equal to n.

Steps:

• Generate all prime numbers up to n using the Sieve of Eratosthenes.

• Iterate through the list of primes and check for each pair (x, y) where x + y = n.

• Store all such valid pairs and return them sorted by x.

Goal: The input integer n is between 1 and 10^6. The prime numbers must be less than or equal to n.

Steps:

• 1 <= n <= 10^6

Assumptions:

• The value of n is always a positive integer.

• Input: For n = 12

• Explanation: The prime numbers less than or equal to 12 are [2, 3, 5, 7, 11]. The valid prime pairs that sum up to 12 are [5, 7].

• Input: For n = 30

• Explanation: The prime numbers less than or equal to 30 are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. The valid prime pairs that sum up to 30 are [7, 23], [11, 19], and [13, 17].

Approach: The solution involves finding all prime numbers up to n and checking for prime pairs that sum up to n.

Observations:

• We need to identify all prime numbers up to n.

• The Sieve of Eratosthenes is an efficient algorithm to find primes up to a large number.

• Using the Sieve of Eratosthenes, we can generate a list of primes, and then check which pairs of primes sum to n.

Steps:

• Use the Sieve of Eratosthenes to generate all prime numbers up to n.

• Iterate through the primes and check if the sum of any two primes equals n.

• Return all such valid pairs in a sorted order.

Empty Inputs:

• If no prime pairs sum up to n, return an empty list.

Large Inputs:

• For large values of n (up to 10^6), the solution should efficiently handle the prime generation using the Sieve of Eratosthenes.

Special Values:

• For n = 2, there are no prime pairs that sum up to 2.

Constraints:

• Ensure that the solution works efficiently even for large values of n.


vector<vector<int>> findPrimePairs(int n) {

    vector<int> net(n + 1, true);
    net[1] = false;
    for(int i = 2; i < n / 2 + 1; i++)
    for(int j = 2; j * i < n; j++)
        net[j * i] = false;

    map<int, int> mp;
    vector<vector<int>> res;

    for(int i = 1; i < n / 2 + 1; i++)
        if(net[i] && net[n - i]) 
        res.push_back({i, n - i});

    return res;
}

1 : Function Definition

vector<vector<int>> findPrimePairs(int n) {

Defines the function `findPrimePairs` that takes an integer `n` and returns a vector of vector pairs of prime numbers that sum to `n`.

2 : Variable Initialization

    vector<int> net(n + 1, true);

Initializes a boolean vector `net` of size `n + 1`, where each element is initially set to `true`, representing the assumption that each number is prime.

3 : Marking Non-Primes

    net[1] = false;

Sets `net[1]` to `false` because 1 is not a prime number.

4 : Sieve of Eratosthenes Loop 1

    for(int i = 2; i < n / 2 + 1; i++)

Starts a loop from `i = 2` to `n / 2 + 1`, iterating through potential prime numbers.

5 : Sieve of Eratosthenes Loop 2

    for(int j = 2; j * i < n; j++)

Starts an inner loop for each multiple of `i`, marking these multiples as `false` (non-prime).

6 : Marking Multiples as Non-Primes

        net[j * i] = false;

Marks the multiples of `i` as `false` in the `net` vector, indicating they are not prime numbers.

7 : Map Initialization

    map<int, int> mp;

Declares a map `mp`, which is not used in this implementation but could be used for further optimization or storing prime counts.

8 : Result Vector Initialization

    vector<vector<int>> res;

Initializes an empty vector `res` to store pairs of primes that sum up to `n`.

9 : Prime Pair Search Loop

    for(int i = 1; i < n / 2 + 1; i++)

Starts a loop to iterate through numbers `i` from 1 to `n / 2`. This is to find pairs where `i` and `n - i` are both prime.

10 : Prime Pair Check

        if(net[i] && net[n - i])

Checks if both `i` and `n - i` are prime numbers by checking their corresponding values in the `net` array.

11 : Store Valid Prime Pair

        res.push_back({i, n - i});

If both `i` and `n - i` are prime, the pair is added to the result vector `res`.

12 : Return Result

    return res;

Returns the vector `res`, which contains all pairs of prime numbers that sum to `n`.

Best Case: O(n log log n) for the Sieve of Eratosthenes.

Average Case: O(n log log n).

Worst Case: O(n log log n).

Description: The time complexity is dominated by the Sieve of Eratosthenes, which runs in O(n log log n). Checking pairs takes O(n) time.

Best Case: O(n).

Worst Case: O(n).

Description: The space complexity is O(n) for storing the prime numbers and their sieve.

Leetcode 2761: Prime Pairs With Target Sum

Explore →