CONSPRIMESUM Editorial

editorial
1

Problem Explanation

We are given an integer N and we have to output the number of prime numbers in the range (3, N) which can be expressed as sum of other consecutive prime numbers from 2.

Approach

We use Sieve of Eratosthenes algorithm to precompute all the prime numbers and consecutive iterate through the list of prime numbers and add them to a sum variable. If the sum is also a prime we increase our count. After the iteration we output the count.

Code

#include <bits/stdc++.h>

using namespace std;

const int LIMIT = 1e5 + 1;

vector < bool > isPrime(LIMIT, true);
vector < int > primes;

int main() {
    for (int i = 2; i * i <= LIMIT; i++)
    {
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < LIMIT; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sum = 5;
        int i = 2;
        int count = 0;
        while (sum <= n) {
            if (isPrime[sum]) {
                count++;
            }
            sum += primes[i];
            i++;
        }
        cout << count << endl;
    }
}