Express a number as a sum of consecutive primes (How many ways?)

I found this problem on codeforces in an ACM archive.

Given a number $n$, find the number possible of ways of expressing that number as a sum of consecutive primes. Example :

Given $n = 41$:

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

As we can see, there are three ways of writing $41$ as a sum of consecutive primes, keeping in mind that since $41$ is a prime, a sum that consists of only $41$ is a valid sum as well.

Knowing that $n \leq 10000$, list the number of ways you can express the input numbers as sums of consecutive primes.

My effort regarding this problem consists of the following :

Given that the max $n $ is $10000 $, I populated a vector of primes using the sieve of eratosthenes (its size is precisely $1229$).

Following, I computed a vector of prefix sums, such that at index $p$ of that particular vector, we have the sum of all consecutive primes up to inclusively $p$ (non prime indexed entries are equal to $0$).

For example: $\text{prime_sums[2] = 2 }, \text{ prime_sums[3] =5 },\text{ prime_sums[5] = 10}$, etc.

Now, using this particular vector we could simply do traversals of the sum array for each of the input numbers and upon finding a way to write it as a sum (by comparing its value with that of each sum we encounter) , we would do multiple subtractions between elements of the sum array in order to find other possible ways to express our number as a sum of consecutive primes.

But this kills the speed of the program and feels really inelegant and awkward. Can you suggest alternative ways?

I assume that n is large, and that we only want the answer for one single n. In that case, we would avoid creating a sieve of all the primes up to n, if possible, because it would take O (n); I think we can do this faster.

Create a list of all primes p ≤ M, using a sieve, with a cleverly chosen M. This takes about O (M) and finds about $M / \ln M$ primes. Then we find all solutions involving primes up to M by adding up primes starting with p = 2 until the sum is ≥ n, recording a solution if the sum equals n, removing the first primes until the sum is M
to the list (which we don't have). At that point we know that the sum of the K largest primes ≤ M is less than s, for some K, and that we have found every possible way to write n as the sum of more than K primes. Now we have to find ways to write n as the sum of k ≤ K consecutive primes; in addition k is odd if n is odd, and k is even if n is even.

For every k, we do this by creating a sieve of primes around n / k; this sieve should be large enough to contain more than k primes. When we have the sieve, we find the first k/2 primes > n/k and k - k/2 primes ≤ n/k. If the sum is less than n then we add the next larger prime and remove the smallest one until the sum is ≥ n; if the sum is > n then we add the next smaller prime and remove the next larger one until the sum is ≤ n. If the sieve turns out to be to small we create a bigger one. If the sum is n, we have a solution.

Creating the sieve takes at least O ($(n/k)^{1/2} / \log n$) steps for trial divisions. Instead of creating the sieve around n/k, we could have made the original sieve larger, choosing M ≈ n / (k - 2) instead of M ≈ n / k, which would have cost about $n / k^2$ steps.

Both costs balance when $n / k^2 = (n/k)^{1/2} / \log n$ or $n^{1/2} = k^{3/2} / \log n$ or $n \log^2 n = k^3$ or $k = (n \log^2 n)^{1/3}$ or $M = n/k = (n \div \log n)^{2/3}$

The estimate for creating the small sieves may have been a bit generous; if we use this method with $M = n^{2/3}$ then it should run in $O (n^{2/3})$.

StackExchange Computer Science Q#65768, answer score: 2