Project Euler＃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 這是鏈接到的問題。

所以，我試圖解決這個問題使用Eratosthenes篩。 我預先計算下面所有素數10^6這是N.

6的給定限制出的7測試用例被接受但最後測試用例給超時（TLE）。

我閱讀討論論壇，他們說，爲了解決這個問題，我們還需要預先計算素數的總和。

所以，我試着製作一個長長整數的數組，並嘗試存儲所有的和。但是這給了我一個分段錯誤。

那麼，我該如何預先計算總理的總和呢？

這裏是我的代碼：

#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[]一起在primes上運行二進制搜索，如果搜索的數字是質數，則在相同位置選擇sum;如果數字不是質數，則在前一位置選擇sum。