Lexicographically smallest prime pair with target sum

Problem

Given an even number n (greater than 2), return two prime numbers whose sum is equal to n.

If there are multiple solutions, return the lexicographically smallest pair [a, b] (with a <= b).

This is guaranteed to have a solution (see Goldbach’s conjecture).

Examples

Example 1

Input: 4
Output: [2, 2]
Explanation: 2 + 2 = 4

Example 2

Input: 10
Output: [3, 7]
Explanation: 3 + 7 = 10 and [3, 7] is lexicographically smallest.

Constraints

• n is an even integer greater than 2.

Solution

Method 1 – Sieve of Eratosthenes and Two Pointer Search

Intuition

To efficiently check for primes up to n, use the Sieve of Eratosthenes. For each a from 2 to n/2, check if both a and n-a are prime. The first such pair is the lexicographically smallest.

Approach

1. Generate all primes up to n using the Sieve of Eratosthenes.
2. For each a from 2 to n/2:
   • If both a and n-a are prime, return [a, n-a].

Code

C++

class Solution {
public:
	vector<int> primePairSum(int n) {
		vector<bool> isPrime(n+1, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i <= n; ++i) {
			if (isPrime[i]) {
				for (int j = i * i; j <= n; j += i) isPrime[j] = false;
			}
		}
		for (int a = 2; a <= n/2; ++a) {
			if (isPrime[a] && isPrime[n-a]) return {a, n-a};
		}
		return {};
	}
};

Java

class Solution {
	public int[] primePairSum(int n) {
		boolean[] isPrime = new boolean[n+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i <= n; ++i) {
			if (isPrime[i]) {
				for (int j = i*i; j <= n; j += i) isPrime[j] = false;
			}
		}
		for (int a = 2; a <= n/2; ++a) {
			if (isPrime[a] && isPrime[n-a]) return new int[]{a, n-a};
		}
		return new int[0];
	}
}

Python

class Solution:
	def prime_pair_sum(self, n: int) -> list[int]:
		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
		for a in range(2, n//2+1):
			if is_prime[a] and is_prime[n-a]:
				return [a, n-a]
		return []

Complexity

• ⏰ Time complexity: O(n log log n) for sieve, O(n) for search — overall O(n log log n).
• 🧺 Space complexity: O(n) — for the sieve array.