Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2873. Prime Pairs With Target Sum

My accepted Python solution to LeetCode problem 2873, Prime Pairs With Target Sum, running in 2298ms.

  • Difficulty: Medium
  • Python
  • Runtime 2298ms
  • Memory 34.8MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 2298ms, memory 34.8MB, accepted 2026-01-01.

python
class Solution:
    def findPrimePairs(self, n: int) -> List[List[int]]:
        # Sieve of Eratosthenes
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for j in range(i*i, n + 1, i):
                    is_prime[j] = False
        
        result = []
        for x in range(2, n // 2 + 1):
            y = n - x
            if is_prime[x] and is_prime[y]:
                result.append([x, y])
        
        return result

Source