题解 | #Sum of Consecutive Prime Numbers#

【Sum of Consecutive Prime Numbers】

$4\times 10^{7}4\backslash times\; 10^7$​​​内有$24336542433654$​​​个素数（可以用欧拉筛在$O(4\times 10^7)O(4\backslash times\; 10^7)$的时间内求出）。

题目保证$T\le 1000,\sum n\le 4\times 10^{7}T\backslash le\; 1000,\backslash sum\; n\backslash le\; 4\backslash times\; 10^7$​​​，

对于每次查询$nn$​​​，可以用双指针维护连续的素数和，暴力的话是$2.4\times 10^6\times 10^{3}2.4\backslash times\; 10^6\backslash times\; 10^3$​会超时，可以考虑减枝操作。

#include <bits/stdc++.h>
using namespace std;

const int N = 4e7 + 10;
int prime[N], vis[N], total;

void Prime() {	// 欧拉筛
    vis[1] = 1;
    for (int i = 2; i <= N - 10; i++) {
        if (!vis[i]) prime[++total] = i;
        for (int j = 1; j <= total && i * prime[j] <= N - 10; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;// 保证每个数只被筛一次
        }
    }
}

int main() {
    Prime();
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int l = 1, r = 0, sum = 0, res = 0;
        while (r + 1 <= total && prime[r + 1] <= n) {	// 减枝
            while (r + 1 <= total && sum < n) {
                sum += prime[++r];
            }
            while (l <= r && sum > n) {
                sum -= prime[l++];
            }
            if (sum == n) res++, sum -= prime[l++];
        }
        printf("%d\n", res);
    }

    return 0;
}