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:
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 | |
Answer: 997651