Consecutive Prime Sum

Problem

Problem Link

The prime $41$, can be written as the sum of six consecutive primes:

$41=2+3+5+7+11+13$.

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains $21$ terms, and is equal to $953$.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Solution

CodeCPP fileDownload

#include <algorithm>
#include <iostream>
#include <vector>
 
std::vector<int> generate_primes(int n) {
  std::vector<bool> is_prime(n + 1, true);
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
      for (int j = i * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  std::vector<int> primes;
  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      primes.push_back(i);
    }
  }
  return primes;
}
 
int main(void) {
  std::vector<int> primes = generate_primes(1000000);
 
  int max_prime = 0, max_length = 0;
  for (size_t i = 0; i < primes.size(); ++i) {
    int sum = 0;
    for (size_t j = i; j < primes.size(); ++j) {
      sum += primes[j];
      if (sum > 1000000) {
        break;
      }
      if (std::binary_search(primes.begin(), primes.end(), sum)) {
        int length = j - i + 1;
        if (length > max_length) {
          max_prime = sum;
          max_length = length;
        }
      }
    }
  }
  std::cout << max_prime << std::endl;
  return 0;
}