Given a number n, find out if n can be expressed as a+b, where both a and b are prime numbers. If such a pair exists, return the values of a and b, otherwise return [-1,-1] as an array of size 2.
Note: If [a, b] is one solution with a <= b, and [c, d] is another solution with c <= d, and a < c then [a, b] is considered as our answer.
Examples
Input: n = 10 Output: 3 7 Explanation: There are two possiblities 3, 7 & 5, 5 are both prime & their sum is 10, but we'll pick 3, 7 as 3 < 5.
Input: n = 3 Output: -1 -1 Explanation: There are no solutions to the number 3.
Expected Time Complexity: O(n*loglog(n))
Expected Auxiliary Space: O(n)
Constraints:
2 <= n <= 106
Approach 01:
-
C++
-
Python
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> getPrimes(int n) {
vector<int> result(2, -1); // Initialize with -1 indicating no pair found
if (n <= 2)
return result; // No prime pair for n <= 2
vector<bool> is_prime(n + 1, true); // Initialize all numbers as prime
is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime numbers
// Sieve of Eratosthenes algorithm to find primes up to n
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false; // Mark multiples of i as non-prime
}
}
}
// Find the prime pair (x, y) such that x + y = n
for (int x = 2; x <= n / 2; ++x) {
int y = n - x;
if (is_prime[x] && is_prime[y]) {
// If both x and y are prime, store them in result and return
result[0] = x;
result[1] = y;
return result;
}
}
return result; // Return {-1, -1} if no prime pair found
}
};
class Solution:
def getPrimes(self, n: int) -> list:
result = [-1, -1] # Initialize with -1 indicating no pair found
if n <= 2:
return result # No prime pair for n <= 2
is_prime = [True] * (n + 1) # Initialize all numbers as prime
is_prime[0] = is_prime[1] = False # 0 and 1 are not prime numbers
# Sieve of Eratosthenes algorithm to find primes up to n
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 # Mark multiples of i as non-prime
# Find the prime pair (x, y) such that x + y = n
for x in range(2, n // 2 + 1):
y = n - x
if is_prime[x] and is_prime[y]:
# If both x and y are prime, store them in result and return
result[0] = x
result[1] = y
return result
return result # Return [-1, -1] if no prime pair found
Complexity:
- Time Complexity:
- Space Complexity: