In Project Euler problem $50,$ the goal is to find the longest sum of consecutive primes that add to a prime less than $1,000,000. $
I have an efficient algorithm to generate a set of primes between $0$ and $N.$
My first algorithm to try this was to brute force it, but that was impossible.
I tried creating a sliding window, but it took much too long to even begin to cover the problem space.
I got to some primes that were summed by $100$+ consecutive primes, but had only run about $5$–$10$% of the problem space.
I'm self-taught, with very little post-secondary education.
Where can I read about or find about an algorithm for efficiently calculating these consecutive primes?
I'm not looking for an answer, but indeed, more for pointers as to what I should be looking for and learning about in order to solve this myself.
Best Answer
To flesh out a comment: the key insight for speeding up this problem is that by using $O(n)$ space, the intermediate sums can be calculated in constant time each: $S_{m,n} = S_{1,n}-S_{1,(m-1)}$, so storing partial sums from $1$ to $i$ lets all other partial sums be easily computed. This removes an $O(n)$ factor from the running time and makes the problem much more tractable.