题意分析

对于每个输入正整数 $n$（$2 \le n \le 10000$），统计有多少种方法将它表示为一个或多个连续质数之和。

解题思路

1. 先用埃氏筛预处理出所有不超过 10000 的质数，存入数组 primes。

2. 对于每个目标值 $n$，使用双指针（滑动窗口）在 primes 上维护区间和：

   • 用左右指针 $L,R$ 和当前和 $S$，初始 $L=0,R=0,S=0$；
   • 当 $S < n$ 且 $R<|\text{primes}|$ 时，$S += \text{primes}[R++]$；
   • 若 $S = n$，答案计数加 1；
   • 然后将 $S -= \text{primes}[L++]$，继续上述过程，直到 $S < n$ 且无法扩展。

本题代码

#include <cstdio>
#include <vector>
using namespace std;

vector<int> primeVector;
void sievePrimes() {
    const int MAXV = 10000;
    static bool isPrime[MAXV+1];
    for (int i = 2; i <= MAXV; i++) isPrime[i] = true;
    for (int i = 2; i*i <= MAXV; i++) {
        if (!isPrime[i]) continue;
        for (int j = i*i; j <= MAXV; j += i)
            isPrime[j] = false;
    }
    for (int i = 2; i <= MAXV; i++) {
        if (isPrime[i])
            primeVector.push_back(i);
    }
}

int num;
void solve() {
    int count = 0;
    int sum = 0;
    size_t left = 0, right = 0;
    while (true) {
        while (sum < num && right < primeVector.size()) {
            sum += primeVector[right++];
        }
        if (sum < num) break;
        if (sum == num) count++;
        sum -= primeVector[left++]; 
    }
    printf("%d\n", count);
}

int main() {
    sievePrimes(); 

    while (scanf("%d", &num) == 1 && num) {
        solve();
    }
    return 0;
}