Sunday, October 23, 2016

UVA 1210 - Sum of Consecutive Prime Numbers

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define LL long long
using namespace std;
vector<int>prime;
bool isPrime(int n)
{
    if(n == 1) return false;
    if(n == 2) return true;
    int sqr = sqrt(n);

    for (int i = 2; i <= sqr; i++)
    {
        if(n%i == 0){

            return false;
        }
    }
    return true;
}
void primeGenerate(int n)
{
    if(isPrime(n))prime.push_back(n);
    if(n > 10000)return;
    n+=1;
    primeGenerate(n);
}
int main()
{
   ios_base::sync_with_stdio(false);
   primeGenerate(1);
   int cnt=0, val;
   while(cin >> val && val){
   bool equal = false;
   for (int i = 0; i < prime.size(); ++i)
   {
        int total = 0;
       for (int j = i; j < prime.size(); ++j)
       {
           total+=prime[j];
           if(total == val){
            cnt++;
           }
           if(total > val)break;
       }
       if(prime[i] > val)break;
   }
   cout << cnt << '\n';
   cnt = 0;
}

return 0;
}

No comments:

Post a Comment