Poj 2739: Sum of Consecutive Prime Numbers

poj2739.md

Poj 2739: Sum of Consecutive Prime Numbers

題目

分析

爬行法…

先建質數表，然後在質數表上爬行。

我們可以用爬行法（在質數表 primes 上爬行），因為

單調性： sum(primes[l, r]) >= sum(primes[l+1, r])

(1) 如果 sum(primes[l, r]) < q，因單調性，所以移動右端點，直到 sum >= q， 在移動的過程中，sum 最終停在 >= q 的最小值上，此時我們判斷 sum == q

(2) 如果 sum(primes[l, r]) >= T，則顯然易見地 sum(primes[l, r+]) 不可能等於 q。

AC code

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N = 10000;
int Np;
bool is_prime[N];
vector<int> primes;

void init_primes() {
    fill(is_prime, is_prime + N, true);
    for (int i = 2; i < N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < N; j += i)
                is_prime[j] = false;
        }
    }
    Np = primes.size();
}

int solve(const int q) {
    long long sum = 0;
    int l = 0, r = 0, cnt = 0;

    for (;;) {
        while (r < Np && sum < q) {
            sum += primes[r++];
        }

        if (sum < q)
            break;
        if (sum == q)
            cnt++;

        sum -= primes[l++];
    }

    return cnt;
}

int main() {
    init_primes();
    int q;
    while (scanf("%d", &q)) {
        if (q == 0) break;
        printf("%d\n", solve(q));
    }

    return 0;
}