#include <iostream>
#include <math.h>
using namespace std;

const int NBR_OF_PRIMES = 128;

/*
 * This C++ program checks to see if an integer is the
 * sum of two or more consecutive primes.
 *
 * @creator gdt
 * @created 2009.11.24
 * @caveats Void of error checking. 
 * @note Created during a CSC100 class at SCC.
 *       The program demonstrates the use of the built-in
 *       (i.e. language supported) array data structure.
 * @see http://azfoo.net/math/consecutiveprimes/
 */

int main(int argc, char* argv[]) {
   bool isprime(int);
   if (argc != 2) {
      cout << "Usage: " << argv[0] << " integer_number" << endl;
      cout << "Prints if input equals the sum of 2 or more"
           << " consecutive prime numbers" << endl;
      return 0;
   }
   int primes[NBR_OF_PRIMES];
   primes[0] = 2;
   int primes_i = 1;
   int n = 3;
   while (primes_i < NBR_OF_PRIMES) {
      if (isprime(n)) {
         primes[primes_i] = n;
         primes_i++;
      }
      n += 2;
   }
   n = atoi(argv[1]);
   int sum = 0;
   int last_i = 0;
   primes_i = 0;
   while (last_i < NBR_OF_PRIMES) {
      if (primes_i >= NBR_OF_PRIMES)
         break;
      while (sum < n) {
         sum += primes[primes_i];
         primes_i++;
      }
      if (sum == n) {
         cout << n << " is the sum of " << primes_i-last_i 
              <<" consecutive primes" << endl << n << " = ";
         while (last_i < primes_i) {
            cout << primes[last_i]; 
            last_i++;
            if (last_i != primes_i) cout << " + ";
         }
         cout << endl;
         return 0;
      }
      last_i++;
      primes_i = last_i;
      sum = 0;
   }
}
bool isprime(int n) {
   if (n == 2) return true;
   if (n <= 1 || n % 2 == 0) return false;
   int limit = (int)sqrt(double(n)) + 1;
   for (int i = 3; i < limit; i++)
      if (n % i == 0) return false;
   return true;
}