Consecutive Prime Sum — Project Euler (Problem 50)

Many problems in Project Euler relate to working with primes. I use primesieve-python to help solve such problems. It consists of Python bindings for the primesieve C++ library. Generates primes orders of magnitude faster than any pure Python code. Features:

  • Generate a list of primes
  • Count primes and prime k-tuplets
  • Print primes and prime k-tuplets
  • Find the nth prime
  • Iterate over primes using little memory

Anyway, here’s Problem 50 from Project Euler:

ProjectEuler50

Here’s how I did it:

# Question: Which prime, below one-million, can be written as the sum of the most consecutive primes
from primesieve import *
from math import *
# Generate list of primes under a million
primes_under_million = generate_primes(10**6)
# Sum of consecutive primes is of order 0.5(n^2)(logn)
# Calculate 'n' so that sum of consecutive primes is less than a million (and not necessarily prime)
nsum = 1
n = 1
while nsum < 10**6:
nsum = 0.5*(n**2)*(log(n, e))
n += 1
# Calculate index so that sum of first 'index' consecutive primes is under a million and also prime
primes_subset = primes_under_million[:n]
nsum = sum(primes_under_million[:n])
while nsum > 10**6:
n -= 1
nsum = sum(primes_under_million[:n])
primes_sum = 0
index = 0
for i in range(len(primes_subset)):
if i % 2 == 1:
pass
else:
sumprimes = sum(primes_subset[:i])
if sumprimes > primes_sum and sumprimes < 10**6 and sumprimes in primes_under_million:
primes_sum = sumprimes
index = i
# Print out sum of consecutive primes till 'index', index, n
# print primes_sum, index, n
# Check consecutive primes within a range (index to n) such that their number is greater than index and maximum
j = index + 1
start = 0
while j <= n:
while (j-start) >= (n-index):
sumprimes = sum(primes_subset[start:j])
if sumprimes > primes_sum and sumprimes in primes_under_million:
primes_sum = sumprimes
start += 1
j += 1
start = 0
print primes_sum
view raw euler50.py hosted with ❤ by GitHub

Answer: 997651

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s