Mercurial > hg > euler
changeset 14:49c96972949d default tip
#50 rewrite of solution
author | Dominic Cleal <dominic@computerkb.co.uk> |
---|---|
date | Mon, 01 Dec 2008 19:11:55 +0000 |
parents | 836a4ccbcbae |
children | |
files | problem50.py |
diffstat | 1 files changed, 24 insertions(+), 32 deletions(-) [+] |
line wrap: on
line diff
--- a/problem50.py Mon Dec 01 13:14:53 2008 +0000 +++ b/problem50.py Mon Dec 01 19:11:55 2008 +0000 @@ -1,35 +1,27 @@ -import math - -def count(i, min): - for a in range(0, len(p) - min): - t = 0 - for b in range(a, len(p)): - t += p[b] - if t == i: - return b - a + 1 - if t > i: - break - return False +import primes -cmax = 0 -imax = 0 -p = [ 2 ] -i = 3 -while i < 1000: - isp = True - max = int(math.floor(math.sqrt(i))) - for t in p[1:]: - if t > max: +def search(pmax): + cur = { } + max = { } + s = primes.testsieve() + for p in s.sieve(): + if p > pmax: break - if i % t == 0: - isp = False - break - if isp: - p.append(i) - c = count(i, cmax) - if not c == False and c > cmax: - cmax = c - imax = i - print "New max %d with %d conseq" % (i, c) - i += 2 + if p not in cur: + cur[p] = (0, 0) + todel = [] + for i in cur: + cur[i] = (cur[i][0] + 1, cur[i][1] + p) + if cur[i][1] > pmax: + todel.append(i) + elif s.isprime(cur[i][1]): + max[i] = cur[i] + for i in todel: + del cur[i] + retmax = None + for i in max: + if retmax is None or max[i][0] > retmax[0]: + retmax = max[i] + return retmax +print "Max conseq has %d terms, totalling %d" % search(1000000)