欧拉计划 #10 如何预先计算素数和？

Question

这里是问题：

10以下的质数和是2+3+5+7=17。

找出不大于给定 N 的所有素数的总和。

输入格式：第一行包含一个整数 T，即测试用例的数量。接下来的 T 行将包含一个整数 N.

输出格式：在单独的行中打印与每个测试用例对应的值。

约束： 1≤T≤104 1≤N≤106

https://www.hackerrank.com/contests/projecteuler/challenges/euler010 这是问题的link。

所以，我试图用埃拉托色尼筛法来解决这个问题。我预先计算了 10^6 以下的所有素数，这是 N 的给定限制。

7 个测试用例中有 6 个被接受，但最后一个测试用例给出了 Timeout(TLE)。

我看了论坛，他们说为了解决这个问题，我们还需要预先计算素数之和。

因此，我尝试制作一个 long long int 数组，并尝试将所有总和存储在其中。但这给了我一个分段错误。

那么，我该如何预先计算素数之和呢？

这是我的代码：

#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

给定一个素数数组 prime[N]，可以在单个 for 循环中预先计算素数和，如下所示：

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

您可以通过运行在 primes 上进行二进制搜索，并在相同位置选择 sum 来将此数组与 primes[] 一起使用，如果要搜索的数字是素数，如果数字不是素数，则在前面的位置。

欧拉计划 #10 如何预先计算素数和？

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

c++

primes

sieve-of-eratosthenes

c++11