http://poj.org/problem?id=2739
2.Idea
Two Pointers
3.Source
bool isPrime[10001];
bool visited[10001];
vector<int> a;
int n, S;
int s, t;
void solve()
{
int res = 0;
int s = 0, t = 0, sum = 0;
for (;;) {
while (t < n && sum < S) sum += a[t++];
if (sum < S) break;
if (sum == S) res++;
sum -= a[s++];
}
printf("%d\n", res);
}
int main()
{
// get all primes
for (int i = 0; i < 10001; i++) isPrime[i] = true;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < 10001; i++) {
if (isPrime[i]) {
a.push_back(i);
for (int j = 2 * i; j < 10001; j += i) {
isPrime[j] = false;
}
}
}
while (cin >> S)
{
if (!S) break;
n = a.size();
solve();
}
return 0;
}
No comments:
Post a Comment