We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prime Pairs With Target Sum

Number: 2873

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer n, find all pairs of prime numbers [x, y] such that 1 <= x <= y <= n and x + y equals n. The returned list should be sorted in increasing order of x. If no such pairs exist, return an empty array.

Key Insights

  • Use the Sieve of Eratosthenes to efficiently generate all prime numbers up to n.
  • For each prime number x, compute y = n - x and check if y is also prime.
  • Ensure that x <= y to avoid duplicate and reversed pairs.
  • Given the constraints (n up to 10^6), the sieve method is optimal for prime generation.

Space and Time Complexity

Time Complexity: O(n log log n) due to the Sieve of Eratosthenes. Space Complexity: O(n) for storing the boolean sieve array.

Solution

The solution involves two main steps:

  1. Generate a boolean array using the Sieve of Eratosthenes to mark all prime numbers up to n.
  2. Iterate over the numbers from 2 to n. For each number x that is prime, check if its complement y (where y = n - x) is also prime and satisfies x <= y. Add valid pairs to the result.

This approach guarantees that each pair is unique and returned in sorted order by design. Edge cases, like when n is too small to form any prime pairs, are naturally handled by the algorithm.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        # Create a list to mark prime numbers up to n; index represents the number
        isPrime = [True] * (n + 1)
        # Mark 0 and 1 as non-prime
        isPrime[0], isPrime[1] = False, False
        
        # Sieve of Eratosthenes to find all prime numbers up to n
        for i in range(2, int(n**0.5) + 1):
            if isPrime[i]:
                # Mark multiples of i as non-prime
                for j in range(i * i, n + 1, i):
                    isPrime[j] = False
        
        # List to store the resulting prime pairs
        result = []
        # Iterate through possible x values starting from 2
        for x in range(2, n + 1):
            if isPrime[x]:
                y = n - x
                # Ensure that y is not less than x and is within bounds and prime
                if y >= x and y <= n and isPrime[y]:
                    result.append([x, y])
        return result
← Back to All Questions