Project Euler #10 How to pre-calculate sum of primes?

Question

Here is the question:

The sum of the primes below 10 is 2+3+5+7=17.

Find the sum of all the primes not greater than given N.

Input Format : The first line contains an integer T i.e. number of the test cases. The next T lines will contains an integer N.

Output Format : Print the value corresponding to each test case in seperate line.

Constraints : 1≤T≤104 1≤N≤106

https://www.hackerrank.com/contests/projecteuler/challenges/euler010 This is the link to the question.

So, i attempted to solve this question using sieve of Eratosthenes. I pre calculated all primes below 10^6 which is the given limit for N.

6 out of the 7 test cases were accepted but the last test case give Timeout(TLE) .

I read the discussion forum and there they say that in order to solve the question we need to pre-calculate the sums of primes also.

So, i tried making an array of long long ints and tried storing all the sums in it. But this is giving me a segmentation fault.

So, how am I supposed to precalculate the sums of the primes?

Here is my code:

#include "header.h"             //MAX is defined to be 1000000

bool sieve[MAX + 1];        // false = prime, true = composite

int main(void){
    //0 and 1 are not primes
    sieve[0] = sieve[1] = true;
    //input limiting value
    int n = MAX;
    //cross out even numbers
    for(int i = 4; i <= n; i += 2){
        sieve[i] = true;
    }
    //use sieve of eratosthenes
    for(int i = 3; i <= static_cast<int>(sqrt(n)); i += 2){     
        if(sieve[i] == false){                          
            for(int j = i * i; j <= n; j += i)              
                sieve[j] = true;
        }
    }
    long long p, ans = 0;
    int t;
    std::cin >> t;
    while(t--){
        std::cin >> p;
        for(int i = 0; i <= p; ++i)
            if(sieve[i] == false)
                ans += i;
        std::cout << ans << std::endl;
        ans = 0;
    }
    return 0;
}

Answer 1

Given an array of primes prime[N], precomputing sums of primes can be done in a single for loop like this:

int sum[N];
sum[0] = primes[0];
for (int i = 1 ; i < N ; i++) {
    sum[i] = prime[i]+sum[i-1];
}

You can use this array together with primes[] by running a binary search on primes, and picking the sum at the same position if the number being searched is prime, or at the prior position if the number is not prime.