题意

给你一个数字$nn$，问你有多少段连续的素数之和等于$nn$

题解

通过欧拉筛线性时间得到所有的素数，并且求出他们的前缀和，接着通过双指针来求解方案数

超时思路

本来是用unordered_map来做，但是好像常数太大了，导致超时，后面改成双指针就过了

代码

#include<bits/stdc++.h>
using namespace std;
 
#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
const db eps = 1e-9;
const int N = 4e7 + 6;
vector<bool> is_prime(N, 1);
vector<int> primes;

void ES() {
    is_prime[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (is_prime[i]) primes.eb(i);
        for (int j = 0; j < sz(primes) && i * primes[j] < N; ++j) {
            is_prime[i * primes[j]] = 0;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    qc;
    ES();
    int m = sz(primes);
    vector<ll> sum(m + 1);
    rep(i, 1, m + 1) sum[i] = sum[i - 1] + primes[i - 1];
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        int ans = 0;
        for (int l = 1, r = 1; l <= m; ++l) {
            if (primes[r - 1] > n) break;
            while(r <= m && sum[r] - sum[l - 1] < n) ++r;
            if (sum[r] - sum[l - 1] == n) ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}