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?