Project Euler Problem 50: http://projecteuler.net/problem=50

prime-as-sum-of-consecutive-primes.cc

#include <math.h>
#include <stdio.h>
#include <set>

typedef std::set<int> Set;

bool is_prime(int a, Set* primes) {
  for (Set::const_iterator i = primes->begin();
       i != primes->end() && *i <= sqrt(a);
       ++i) {
    if (a % *i == 0) {
      return false;
    }
  }
  return true;
}

void find_primes(int cap, Set* primes) {
  primes->insert(2);
  primes->insert(3);
  primes->insert(5);
  primes->insert(7);
  primes->insert(11);
  for (int i = 12; i < cap; ++i) {
    if (is_prime(i, primes)) {
      primes->insert(i);
    }
  }
}

int main() {
  const int CAP = 1000000;
  Set primes;
  find_primes(CAP, &primes);

  int max_len = 0;
  int max_sum = 0;
  for (Set::const_iterator i = primes.begin(); i != primes.end(); ++i) {
    int sum = *i;
    int len = 1;
    Set::const_iterator ii = i;
    for (Set::const_iterator j = ++ii; sum < CAP && j != primes.end(); ++j) {
      sum += *j;
      len++;
      Set::const_iterator check = primes.find(sum);
      if (check != primes.end()) {
        if (len > max_len) {
          max_len = len;
          max_sum = sum;
        }
      }
    }
  }
  printf("The prime is %d with length %d\n", max_sum, max_len);

  return -1;
}