Wednesday, April 1, 2020

POJ.2739 Sum of Consecutive Prime Numbers

1.Problem
http://poj.org/problem?id=2739

2.Idea
Enumerating primes

3.Source
 const int maxp = 2000;  
 int n = 10000;  
 int prime[maxp], total = 0;  
 bool isPrime(int k)  
 {  
      for (int i = 0; i < total; i++) {  
           if (k % prime[i] == 0) return false;  
      }  
      return true;  
 }  
 int main()  
 {  
      for (int i = 2; i <= n; i++) {  
           if (isPrime(i)) prime[total++] = i;  
      }  
      prime[total] = n + 1;  
      int m;  
      cin >> m;  
      while (m) {  
           int ans = 0;  
           for (int i = 0; m >= prime[i]; i++) {  
                int cnt = 0;  
                for (int j = i; j < total && cnt < m; j++) {  
                     cnt += prime[j];  
                }  
                if (cnt == m) ans++;  
           }  
           cout << ans << endl;  
           cin >> m;  
      }  
      return 0;  
 }  

No comments:

Post a Comment