Project Euler problem 50

Question

I was just trying Project Euler problem 50.

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?

Here's my code for the same in Python:

LIMIT = 1000000

x = [1] * (LIMIT + 1)
x[0] = x[1] = 0

primes = []
length = 0

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        length += 1

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

s = 0
prev = -1
cnt = -1

for i in range(length):
    s = 0

    for j in range(i, length):
        s += primes[j]

        if s > LIMIT:
            break

        if x[s] and cnt < j - i + 1:
            cnt = j - i + 1
            prev = s

print(prev)

I just create a list of primes using Sieve of Eratosthenes. For each prime, I'm just finding all the consecutive primes and their sums to get the answer.

This currently takes about one second to run.

Is there a faster, better, and neater way to solve this?

Thank you for your help!

EDIT:

I see there are 2 votes to close my program as it Lacks concrete context. Can you please explain what I should do to add concrete context?

Answer 1

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        length += 1

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

This is inconsistent: either i should range up to LIMIT inclusive, or there's no need for j to range up to LIMIT inclusive.

Also, updating length in the loop is overkill. len(primes) outside the loop works just as well and doesn't distract.

There are more advanced ways of doing the sieve with range updates, but that's already covered in dozens if not thousands of answers on this site, so I'll leave it as an exercise to search for one of them.

---

s = 0
prev = -1
cnt = -1

It's not immediately clear what any of those variable names mean.

        if x[s] and cnt < j - i + 1:
            cnt = j - i + 1
            prev = s

This could be done more elegantly by folding cnt and prev into a tuple:

width_sum = (-1, -1)

...
    if x[s]:
        width_sum = max(width_sum, (j - i + 1, s))

---

You want the longest, so the fastest approach will usually be to search in decreasing order of length. To keep the bookkeeping simple it may be worth aggregating partial sums:

primes = []
accum = [0]

for i in range(2, LIMIT):
    if x[i]:
        primes.append(i)
        accum.append(accum[-1] + i)

        for j in range(i * i, LIMIT + 1, i):
            x[j] = 0

primes = set(primes)
for width in range(len(primes), 0, -1):
    for off in range(width, len(accum)):
        partial_sum = accum[off] - accum[off - width]
        if partial_sum > LIMIT:
            break
        if partial_sum in primes:
            print(partial_sum)
            exit(0)

Answer 2

Often on project Euler, it is useful to solve a problem "backwards". What do I mean by this? Well, "forwards" would be to generate a list of primes, and check all consecutive sums for primality and length, a "bottom up" approach. This takes a very long time and is rather undirected.

Because you're building up from the smallest length, you need to keep building your consecutive sums, even when you've found potential answers!

---

A better solution would be to start with an ordered list of primes whose sum is below 10**6 (which can easily be generated with a sieve as you have done). Then, put them all together in a list and find the sum. Then, do the following:

• Remove a prime from the beginning
• Check the sum for primality
• Add it back and remove a prime from the end
• Check the sum for primality
• Remove both
• Check the sum for primality
• ...

This means as soon as you find a prime from those sums, you have guaranteed it is the largest, simply by working backwards.

---

Now that you have the basic algorithm, you can start making efficiency improvements. Things like improving your initial sieve; or making optimisations to your python code using generators, fewer function calls etc.

Finally, there are all sorts of great answers on the project Euler forums which you have access to if you submit a correct answer. It's always worth skimming them having completed a problem; there's always someone with a better way of doing it!

---

Pseudocode of example:

I'll show how this algorithm could be used to generate the answer 41 for the largest prime below 100 constructed from consecutive primes.

Using a sieve, generate a list of primes, p whose sum is <= 100: p = [2, 3, 5, 7, 11, 13, 17, 19, 23]

Remove the largest prime from the list and evaluate if the sum is prime:

p -> p = [2, 3, 5, 7, 11, 13, 17, 19]
sum = 77
is_prime(sum) >>> False

Add the largest prime (23) back to the list, remove the smallest prime (2) and try again:

p -> p = [3, 5, 7, 11, 13, 17, 19, 23]
sum = 98
is_prime(sum) >>> False

Add the smallest prime (2) back, then remove the two largest primes (19, 23):

p -> p = [2, 3, 5, 7, 11, 13, 17]
sum = 58
is_prime(sum) >>> False

Add back the largest prime, remove the smallest:

p -> p = [3, 5, 7, 11, 13, 17, 19]
sum = 75
is_prime(sum) >>> False

Add back the smallest, remove the two largest:

p -> p = [2, 3, 5, 7, 11, 13]
sum = 41
is_prime(sum) >>> True
# Success!
return sum