  We present and analyze an algorithm to enumerate all integers $n\le x$ that
can be written as the sum of consecutive $k$th powers of primes, for $k>1$. We
show that the number of such integers $n$ is asymptotically bounded by a
constant times $$ c_k \frac{ x^{2/(k+1)} }{ (\log x)^{2k/(k+1)} }, $$ where
$c_k$ is a constant depending solely on $k$, roughly $k^2$ in magnitude. This
also bounds the asymptotic running time of our algorithm. We also give a lower
bound of the same order of magnitude, and a very fast algorithm that counts
such $n$. Our work extends the previous work by Tongsomporn, Wananiyakul, and
Steuding (2022) who examined sums of squares of consecutive primes.
