N下所有素数的优化求和

Question

eular 项目中有第 10 个问题。

问题是求所有不大于N的素数之和。

我对这个问题的解决方案是：

int solve(int n){

    bool check[n+1];
    for(int i=0;i<=n;i++){
        check[i]=true;
    }

    for(int i=2;i*i<=n;i++){
        if(check[i]){
            for(int j=i*i;j<=n;j+=i){
                check[j]=false;
            }
        }
    }

    int sum=0;
    for(int i=2;i<=n;i++){
        if(check[i]){
            sum+=i;
        }
    }
    return sum;
}

但问题仍然没有得到足够的优化，因为我收到了“由于超时而终止”的消息。

我怎样才能更好地优化这段代码。

限制条件是：

1<= T <= 10^4 ( T 是测试用例的数量 )

1<=N<=10^6

你可以在这里自己尝试一下

Answer 1

您的 T 最多为 10^4（测试数量），并且对于每个测试，您都solve()从头开始运行。

只需运行solve()一次以获得最大可能n，并将结果check和sums数组保存到全局变量中，以便稍后重用它们。然后在每个测试用例上返回sums[n]。

另外，不要忘记小于最大 N（100 万）的素数之和等于37550402023，这会溢出最大可能int值，因此您必须使用 64 位int64_t来求和。

根据我上面的建议，下面是您的代码，需要进行最少的修改才能使其非常快：

在线尝试一下！

#include <cstdint>
#include <iostream>

enum { max_n = 1000000 };
bool check[max_n+1] = {};
int64_t sums[max_n+1] = {};

void solve() {
    for(int i=0;i<=max_n;i++){
        check[i]=true;
    }

    for(int i=2;i*i<=max_n;i++){
        if(check[i]){
            for(int j=i*i;j<=max_n;j+=i){
                check[j]=false;
            }
        }
    }

    int64_t sum=0;
    for(int i=2;i<=max_n;i++){
        if(check[i]){
            sum+=i;
        }
        sums[i] = sum;
    }
}

int main() {
    solve();

    int ntests = 0;
    std::cin >> ntests;
    for (int i = 0; i < ntests; ++i) {
        int n = 0;
        std::cin >> n;
        std::cout << sums[n] << std::endl;
    }    
}

输入：

6
10
100
1000
10000
100000
1000000

输出：

17
1060
76127
5736396
454396537
37550402023