Problem

Given an even number (greater than 2), return two prime numbers whose sum will be equal to the given number. A solution will always exist as per Goldbach’s conjecture. If there are multiple solutions possible, return the lexicographically smaller solution. If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, then [a, b] < [c, d] if and only if a < c or a == c and b < d.

Examples

Examle 1

1
2
3

Input: 4
Output: 2 + 2 = 4
Explanation: The only pair of prime numbers that sum up to 4 is (2, 2).

Examle 2

1
2
3

Input: 10
Output: 3 + 7 = 10
Explanation: The valid pairs are (3, 7) and (5, 5). According to lexicographical order (3, 7) < (5, 5). Hence, the output is 3 + 7 = 10.

Solution

Method 1 - Using Goldbach’s conjecture and Sieve of Eratosthenes

The approach is based on Goldbach’s conjecture that every even number greater than 2 can be expressed as the sum of two prime numbers. We’ll generate all prime numbers up to the given number using the Sieve of Eratosthenes technique and check pairs of these primes to find the required pair that sums up to the given number.

Here is the approach:

  1. Generate Prime Numbers: Use the Sieve of Eratosthenes to generate a list of prime numbers up to the given number.
  2. Find Prime Pair: Iterate over the list of prime numbers and for each prime p, check if number - p is also a prime.
  3. Return Lexicographically Smallest Pair: Ensure the pair [a, b] such that a <= b is the lexicographically smallest pair found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {
    public int[] findPrimePairSum(int n) {
        boolean[] isPrime = sieveOfEratosthenes(n);
        for (int i = 2; i <= n / 2; i++) {
            if (isPrime[i] && isPrime[n - i]) {
                return new int[]{i, n - i};
            }
        }
        return new int[0]; // just a fallback, per problem statement this won't happen
    }

    private boolean[] sieveOfEratosthenes(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;
                }
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 10;
        int[] result = solution.findPrimePairSum(n);
        System.out.println(result[0] + " + " + result[1] + " = " + n);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def findPrimePairSum(self, n: int):
        is_prime = self.sieve_of_eratosthenes(n)
        for i in range(2, n // 2 + 1):
            if is_prime[i] and is_prime[n - i]:
                return i, n - i
        return None

    def sieve_of_eratosthenes(self, n: int):
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        p = 2
        while p * p <= n:
            if is_prime[p]:
                for i in range(p * p, n + 1, p):
                    is_prime[i] = False
            p += 1
        return is_prime

# Example usage
solution = Solution()
n = 10
result = solution.findPrimePairSum(n)
print(f"{result[0]} + {result[1]} = {n}")

Complexity

  • ⏰ Time complexity: O(n log log n)
    • Generating prime numbers using the Sieve of Eratosthenes takes O(n log log n).
    • Checking pairs takes up to O(n/2), which is O(n) in the worst case.
  • 🧺 Space complexity: O(n) for storing the boolean array which indicates primality.