project-euler/problem50.py at master · rayleyva/project-euler · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import math

def is_prime(n):
    if n < 2:
        return False
    if n != 2 and n % 2 == 0:
        return False
    for j in xrange(3, math.sqrt(n) + 1, 2):
        if n % j == 0:
            return False
    return True

target = 1000000 # this is the max sum

cur_sequence = 0
max_sequence = 0
cur_sum = 0
max_sum = 0

# the highest number we should check is going to be approx
# 1,000,000 divided by the max number of items in the longest
# sequence, so guess the smallest number expected
min_expected = 100

primes = [2]
i = 3
while i < (target / min_expected):
    if is_prime(i):
        primes.append(i)
    i += 2

i = 0
while i < (len(primes) - max_sequence):
    cur_sum = primes[i]
    for j in xrange(len(primes) - 1, i, -1):
        if sum(primes[i:j]) < target:
            if is_prime(sum(primes[i:j])):
                cur_sequence = j - i
                cur_sum = sum(primes[i:j])
                break
    if cur_sequence > max_sequence:
        max_sequence = cur_sequence
        max_sum = cur_sum
    i += 1

print '%d: %d' % (max_sum, max_sequence)