Sum of Consecutive Prime Numbers POJ2739

投稿日：2022/12/24 更新日:2022/12/24

POJ

競プロ

問題：http://poj.org/problem?id=2739

問題

いくつかの正整数は連続した素数の和で表すことができる。また、表し方もいくつかある。正整数が与えられるので合計でいくつの表し方があるのかを示してください。

解法

与えられる整数 $x$ は $2 \leqq x \leqq 10000$ であるので、その範囲の素数を列挙して尺取り法を行えば良い。

素数の列挙はエラトステネスのふるいを用いると高速にできる。

尺取り法の実装には複数やり方があるが、今回は「while1重尺取り法」を用いた。

実装

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

const int MAX = 10000;

void solve(){
    vector<bool> is_prime(MAX+1, true);
    is_prime[0] = is_prime[1] = false;

    for(int i = 2;i <= MAX; ++i){
        if(!is_prime[i])continue;
        for(int k = 2*i;k <= MAX; k += i){
            is_prime[k] = false;
        }
    }

    vector<int> primes;
    for(int i = 2;i <= MAX; ++i){
        if(is_prime[i]){
            primes.push_back(i);
        }
    }
    int m = primes.size();


    int x;
    cin >> x;
    while(x != 0){
        int l = 0, r = 0;
        int sum = 0;
        int ans = 0;
        while(l < m){
            if(sum == x){
                ans++;
            }
            if(r < m && sum < x){
                sum += primes[r];
                r++;
            }else{
                sum -= primes[l];
                l++;
            }
        }

        cout << ans << '\n';

        cin >> x;
    }
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
    return 0;
}