Question

I m trying to solve problem 50 on Project Euler. Don t give me the answer or solve it for me, just try to answer this specific question.

The goal is to find the longest sum of consecutive primes that adds to a prime below one million. I wrote a sieve to find all the primes below n, and I have confirmed that it is correct. Next, I am going to check the sum of each subset of consecutive primes using the following method:

I have a empty list sums. For each prime number, I add it to each element in sums and check the new sum, then I append the prime to sums.

Here it is in python

primes = allPrimesBelow(1000000)
sums = []
for p in primes:
    for i in range(len(sums)):
        sums[i] += p
        check(sums[i])
    sums.append(p)

I want to know if I have called check() for every sum of two or more consecutive primes below one million

The problem says that there is a prime, 953, that can be written as the sum of 21 consecutive primes, but I am not finding it.

Answer 1

Your code is correct. I ran it and it does generate the number 953, so the problem is probably with your prime generating function. There should be 78498 primes below a million - you may want to check if you get that result.

That said, your code will take a long time to run, since it will call check() 3,080,928,753 times. You may want to find a method that checks less sums. I won t expand on this since you asked for no spoilers, but let me know if you re interested in general hints.

Answer 2

I don t have a straight answer off the top of my head, but have you tried making sums into a nested array and then appending primes p to the sub-arrays instead of adding them to a summation counter? That would let you visually check which primes were being added to each sub-array, and by extension would tell you which primes the original code was summing up.

友情链接