Friday, February 21, 2020

POJ.2739 Sum of Consecutive Prime Numbers

1.Problem
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