Solution with bool Sieve of Eratosthenes


#1

This allocates the maximum memory allowed for the problem; if you allocate any more memory than this, you get a memory limit exceeded error. So you need to work directly out of the sieve.

vector Solution::primesum(int A) {
vectorresult;

    if (A > 2) {
        // Sieve of Erathosthenes
        vector<bool> sieve(A, true);
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 2; i < A; i++) {
            if (sieve[i]) {
                int x = i + i;
                while (x < A) {
                    sieve[x] = false;
                    x += i;
                }
            }
        }

        int half = A / 2;
        for (int i = A - 1; i >= half; i--) {
            if (sieve[i] && sieve[A - i]) {
                result.push_back(A - i);
                result.push_back(i);
                break;
            }
         }
    }
    return result;
}