Solution using Sieve of Eratosthenes


#1

vector Solution::primesum(int A) {
vector primes(A+1,true);
primes[0] = false;
primes[1] = false;
int limit = (int)sqrt(A);
for(int i = 2; i <= limit ; i++) {
if(primes[i] == true) {
for(int j = i*i; j < A; j += i) {
primes[j] = false;
}
}
}
vector res;
for(int i = A-1; i >= A/2; i–) {
if(primes[i] && primes[A-i]) {
res.push_back(A-i);
res.push_back(i);
break;
}
}
return res;
}