POJ 2739 Sum of Consecutive Prime Numbers：素數篩與連續和枚舉

POJ 2739 連續素數和 — 素數篩 + 雙指針/暴力枚舉

問題：給定 X (≤10000)，求有多少種方式將 X 表示為連續素數之和。輸入以 0 結束。

解法步驟

1. 埃拉托斯特尼篩法求出所有 ≤10000 的素數，存入 prime[]（約 1229 個）。
2. 對每個查詢 X：
   • 找到第一個 > X 的素數位置 bound（上界），連續和的起始素數必在 bound 之前。
   • 雙層循環枚舉起點 i，累加 sum += prime[j] 直到 sum ≥ X。若 sum == X 計數器 +1。
   • 優化：若 prime[i] > X 可提前結束外層循環。

代碼實現

const int MAXN = 10000;
vector primes;
bool is_composite[MAXN+1];

void sieve() {
    for (int i = 2; i <= MAXN; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > MAXN) break;
            is_composite[i * p] = true;
            if (i % p == 0) break; // 線性篩優化
        }
    }
}

int main() {
    sieve();
    int x;
    while (cin >> x && x) {
        if (x < 2) { cout << 0 << '\n'; continue; }
        int bound = upper_bound(primes.begin(), primes.end(), x) - primes.begin();
        int ans = 0;
        for (int i = 0; i < bound; ++i) {
            int sum = 0;
            for (int j = i; j < bound; ++j) {
                sum += primes[j];
                if (sum == x) { ++ans; break; }
                if (sum > x) break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 篩法：O(N log log N) 或線性 O(N)，N=10000 瞬間完成。
• 查詢：最壞 O(P²)，P≈1229，但內層提前中斷，實際極快。多組測試總時間 < 10ms。

關鍵點

• 連續素數和的起點必 ≤ X，終點也 ≤ X（因素數 ≥ 2）。
• 若 X 本身是素數，單個素數也算一種表示（i=j）。
• 線性篩（歐拉篩）可避免重複標記，更優雅。