欧拉计划第10题：N以内质数求和代码超时问题的优化方案咨询

嘿，我一眼就看出问题所在了——你的代码每次处理测试用例都要重新跑一遍埃氏筛，在T=1e4的情况下，重复计算的开销直接把时间拉爆了！再加上几个细节没处理好，超时简直是必然的。咱们来一步步把它优化到能通过所有测试用例：

核心优化：预计算前缀和数组 #

这是解决多测试用例超时的关键！既然N的最大值是1e6，我们完全可以在程序启动时一次性筛出1e6以内的所有质数，同时计算出前缀和数组。这样每个测试用例只需要O(1)时间查询结果，总时间复杂度从O(T*N log log N)直接降到O(N log log N + T)，效率提升几个数量级。

必须修复的细节问题 #

• 栈溢出风险：你在函数里声明的bool check[n+1]是栈上的变长数组，当n=1e6时，栈空间很可能不够（默认栈大小通常只有几MB）。换成全局数组、静态数组或者vector来存储，这些是在堆上分配空间，完全不用担心溢出。
• 整数溢出：1e6以内所有质数的和是37550402023，远超过int的最大值（约2e9），必须用long long来存储总和和前缀和，否则结果会直接错误。

筛法的极致优化（可选） #

如果还想进一步压缩时间和空间，可以用奇偶筛——除了2之外，所有质数都是奇数，我们只需要处理奇数的状态，这样空间能减半，时间也能节省不少。

优化后的完整代码示例 #

基础优化版（足够通过测试用例） #

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX_LIMIT = 1e6;
vector<bool> is_prime(MAX_LIMIT + 1, true);
vector<long long> prime_prefix_sum(MAX_LIMIT + 1, 0);

void precompute_primes() {
    // 0和1不是质数
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= MAX_LIMIT; ++i) {
        if (is_prime[i]) {
            // 从i*i开始标记非质数，避免重复标记
            for (int j = i * i; j <= MAX_LIMIT; j += i) {
                is_prime[j] = false;
            }
        }
    }
    // 计算前缀和
    long long total = 0;
    for (int i = 0; i <= MAX_LIMIT; ++i) {
        if (is_prime[i]) {
            total += i;
        }
        prime_prefix_sum[i] = total;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快输入输出速度，应对1e4次测试用例
    
    precompute_primes(); // 只执行一次预计算
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << prime_prefix_sum[n] << '\n';
    }
    return 0;
}

极致优化的奇偶筛版 #

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX_LIMIT = 1e6;
// 只存储奇数的质数状态，索引i对应数字2i+1
vector<bool> is_prime((MAX_LIMIT + 1) / 2, true);
vector<long long> prime_prefix_sum(MAX_LIMIT + 1, 0);

void precompute_primes() {
    is_prime[0] = false; // 对应数字1，非质数
    prime_prefix_sum[0] = 0;
    prime_prefix_sum[1] = 0;
    prime_prefix_sum[2] = 2; // 唯一的偶质数
    
    long long total = 2;
    int sqrt_limit = sqrt(MAX_LIMIT);
    int max_i = (sqrt_limit - 1) / 2;
    
    // 筛奇数质数
    for (int i = 1; i <= max_i; ++i) {
        if (is_prime[i]) {
            int p = 2 * i + 1;
            // 从p*p开始标记，p*p是奇数，对应索引为(p*p - 1)/2
            int start = (p * p - 1) / 2;
            for (int j = start; j <= (MAX_LIMIT - 1) / 2; j += p) {
                is_prime[j] = false;
            }
        }
    }
    
    // 填充前缀和数组
    for (int i = 3; i <= MAX_LIMIT; ++i) {
        prime_prefix_sum[i] = prime_prefix_sum[i - 1];
        if (i % 2 == 1 && is_prime[(i - 1) / 2]) {
            total += i;
            prime_prefix_sum[i] = total;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    precompute_primes();
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << prime_prefix_sum[n] << '\n';
    }
    return 0;
}

额外小技巧 #

加上ios::sync_with_stdio(false); cin.tie(nullptr);可以大幅加快C++的输入输出速度，应对1e4次测试用例的输入需求，避免因为IO慢导致的超时。

内容的提问来源于stack exchange，提问作者Nitish