Problem #50 involves sums of consecutive primes. The question reads:
Project Euler Problem 50: Consecutive prime sum
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?
If you’ve seen my solutions to other Project Euler problems that involve primes, you can probably guess that my solution involves the Sieve of Eratosthenes. Here is my solution:
Solution #1: Brute Force Sieve Approach
We simply iterate through the sums of different numbers of consecutive primes until the minimum sum of the given number of consecutive primes is greater than 1,000,000. We can use a sieve to list all of the primes less than 1,000,000, and we can use binary search to check if a given sum is in the list of primes. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Sieve Approach to Project Euler Problem #50
'''
import time
def sieveEratosthenes(n):
myPrimes = []
primePossible = [True]*(n+1)
primePossible[0] = False
primePossible[1] = False
for (i,possible) in enumerate(primePossible):
if possible:
for x in range(i*i, (n+1), i):
primePossible[x] = False
myPrimes.append(i)
return myPrimes
def binarySearch(myList,v):
lower = 0
upper = len(myList)-1
while(lower<upper-1):
middle = (lower+upper)/2
a = myList[middle]
if a<v:
lower = middle
elif a>v:
upper = middle
else:
return middle
if myList[lower] == v:
return lower
if myList[upper] == v:
return upper
return -1
def projectEulerProblemFifty(n):
allPrimes = sieveEratosthenes(n)
maxPrime = 41
c = 7
while(c<=n):
total = 0
for x in range(c):
total+=allPrimes[x]
if(total>n):
return maxPrime
if(total in allPrimes):
maxPrime = total
a = c
while(a<n):
total+=allPrimes[a]
total-=allPrimes[a-c]
if(total > n):
break
x = binarySearch(allPrimes, total)
if(x>=0):
maxPrime = total
a+=1
c+=1
return maxPrime
start = time.time()
print projectEulerProblemFifty(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
997651
--- 1.33064293861 seconds ---
for input of n = 1000000.
'''
And with that, we’re done. While writing this, I realized that the solution can probably be greatly improved if the number of consecutive primes were to count down from the smallest number n such that the sum of the first n primes is greater than 1,000,000. Unfortunately, I am too lazy to implement this right now. I may come back to this problem eventually.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 