优化后的求解N以内所有质数之和。

Question

在欧拉计划中有第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

您可以在此处尝试它。

- NITISH PANDEY

---

你只需要在第一个问题开始时运行筛子一次，最多到10^6。然后，您可以在不重新计算的情况下将其用于所有其他测试用例。还要检查答案会有多大。sum应该是long类型吗？ - rossum

一些提示：1）确定最大的n值并存储所有小于该值的质数 2）在单次遍历中计算最大n之前的所有和 3）使用长整型变量来保存和。 - Rocco

阅读有关埃拉托色尼筛法快速查找质数的资料，然后了解如何使用前缀和数组预处理求和。 - Praveen Ojha

你也可以用筛法来处理小于 sqrt(n) 的数字。它可以显著加速你的双重循环。 - Sebastian

在10^6以下，只有78,498个质数。你可以使用预先计算好的表格，它的大小不到半兆。 - Raymond Chen

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

- Arty

Answer 2

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>
#include <bitset>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    std::vector<int> qn;
    qn.reserve(t);
    int i, tmp, lim = 0;
    for (i = 0; i != t; ++i) {
        std::cin >> tmp;
        qn.emplace_back(tmp);
        lim = std::max(lim, tmp);
    }
    auto primes = std::make_unique<std::bitset<1000000 + 1>>();
    primes->set();
    primes->set(0, false);
    primes->set(1, false);
    int j;
    for (i = 2; i * i <= lim; ++i) {
        if (primes->test(i)) {
            for (j = i * i; j <= lim; j += i) {
                primes->set(j, false);
            }
        }
    }
    std::vector<long long> ans(lim + 1);
    for (i = 2; i <= lim; ++i) {
        ans[i] = ans[i - 1];
        if (primes->test(i)) {
            ans[i] += i;
        }
    }
    for (auto const& q : qn) {
        std::cout << ans[q] << '\n';
    }
    return 0;
}

读取t。定义qn，它是您要存储问题的向量。使用reserve为t元素分配内存，从而避免预分配。读取您的问题（tmp），将它们存储在qn中，并找出其中最大的一个（lim）。通过unique_ptr primes在堆上分配bitset。对primes运行Eratosthenes筛法算法，直到达到lim。定义向量ans，它是您要存储问题答案的向量。对其运行前缀和算法，即如果数字i不是质数，则将迄今为止累积的总和移动（ans[i] = ans[i - 1];）否则将i添加到新生成的总和中。循环遍历qn并打印每个问题q的答案。

- user17970898