Friday, July 25, 2014

UVa - 1210 - Sum of Consecutive Prime Numbers

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define mx 10000
using namespace std;
bool prime[mx];
int main(){
    vector <int> container;
    for(int i = 2; i <= sqrt(mx); i++)
        if(prime[i] == 0)
        for(int j = i+i; j <= mx; j += i)prime[j] = 1;
    for(int i = 2; i <= mx; i++)if(prime[i] == 0)container.push_back(i);
    int number;
    while(cin >> number){
        if(number == 0)break;
        int ans = 0, flag = 0, output = 0;
        for(int i = 0; ; i++){
            if(container[i] > number)break;
            ans += container[i];
            while(ans > number){
                ans -= container[flag];
                flag++;
            }
            if(ans == number)output++;
            if(container[i] == number)break;
        }
        cout << output << endl;
    }
    return 0;
}

No comments:

Post a Comment