< (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:

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

Code

[{"language":"Java","code":"public class Solution {\n    public int[] findPrimePairSum(int n) {\n        boolean[] isPrime = sieveOfEratosthenes(n);\n        for (int i = 2; i <= n / 2; i++) {\n            if (isPrime[i] && isPrime[n - i]) {\n                return new int[]{i, n - i};\n            }\n        }\n        return new int[0]; // just a fallback, per problem statement this won't happen\n    }\n\n    private boolean[] sieveOfEratosthenes(int n) {\n        boolean[] isPrime = new boolean[n + 1];\n        Arrays.fill(isPrime, true);\n        isPrime[0] = isPrime[1] = false;\n        for (int i = 2; i * i <= n; i++) {\n            if (isPrime[i]) {\n                for (int j = i * i; j <= n; j += i) {\n                    isPrime[j] = false;\n                }\n            }\n        }\n        return isPrime;\n    }\n\n    public static void main(String[] args) {\n        Solution solution = ne

Related Tags