Project Euler problem 50 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 &gt; LIMIT:
            break

        if x[s] and cnt &lt; 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?
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 &lt; 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 &gt; LIMIT:
            break
        if partial_sum in primes:
            print(partial_sum)
            exit(0)