Jack's solution to the sum of consecutive primes problem

gistfile1.py

#! /usr/bin/env python3

import sys

upper_bound = 1000000
# Optionally take the upper bound from the command line.
if len(sys.argv) > 1:
    upper_bound = int(sys.argv[1])

# Computes the list of all primes using Sundaram's Sieve. This is a *lot*
# faster than checking prime factors for divisibility.
# See http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/2073279#2073279
def sundaram_sieve(upper_bound):
    # The bound must be even. Since evens can't be primes, this is ok.
    if (upper_bound % 2 == 1):
        upper_bound += 1
    numbers = list(range(3, upper_bound + 1, 2))
    half_max = upper_bound // 2
    initial = 4
    for step in range(3, upper_bound + 1, 2):
        for i in range(initial, half_max, step):
            numbers[i-1] = 0
        initial += 2 * (step + 1)
        if initial > half_max:
            return [2] + [n for n in numbers if n != 0]

primes_list = sundaram_sieve(upper_bound)

primes_set = set(primes_list)

# Compute the sums of all sequences starting from the beginning, to speed up
# the next part.
sums_list = []
sum_so_far = 0
for p in primes_list:
    sum_so_far += p
    sums_list.append(sum_so_far)

# Check all possible sums of consecutive primes.
max_len = 1
for i in range(len(primes_list)):
    # Only bother with sequences greater than the longest found so far.  This
    # has the consequence that, if there are two sequences of equal length, we
    # will always return the one with the smaller sum.
    for j in range(i + max_len, len(primes_list)):
        sequence_sum = sums_list[j] - (sums_list[i-1] if i > 0 else 0)
        if sequence_sum  > upper_bound:
            break
        if sequence_sum in primes_set:
            max_len = j - i + 1 # inclusive
            max_i = i
            max_j = j
            max_sum = sequence_sum

print("{0} is the sum of {1} primes starting with {2}.".format(
    max_sum,
    max_len,
    primes_list[max_i]))