euler: problem50.py annotate

annotate problem50.py @ 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	fa152d695acd
children

rev	line source
14 49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	1 import primes
0 0e08f4decf67 Adding files from xenon Dominic Cleal <dominic@computerkb.co.uk> parents: diff changeset	2
14 49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	3 def search(pmax):
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	4 cur = { }
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	5 max = { }
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	6 s = primes.testsieve()
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	7 for p in s.sieve():
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	8 if p > pmax:
0 0e08f4decf67 Adding files from xenon Dominic Cleal <dominic@computerkb.co.uk> parents: diff changeset	9 break
14 49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	10 if p not in cur:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	11 cur[p] = (0, 0)
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	12 todel = []
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	13 for i in cur:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	14 cur[i] = (cur[i][0] + 1, cur[i][1] + p)
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	15 if cur[i][1] > pmax:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	16 todel.append(i)
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	17 elif s.isprime(cur[i][1]):
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	18 max[i] = cur[i]
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	19 for i in todel:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	20 del cur[i]
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	21 retmax = None
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	22 for i in max:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	23 if retmax is None or max[i][0] > retmax[0]:
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	24 retmax = max[i]
49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	25 return retmax
0 0e08f4decf67 Adding files from xenon Dominic Cleal <dominic@computerkb.co.uk> parents: diff changeset	26
14 49c96972949d #50 rewrite of solution Dominic Cleal <dominic@computerkb.co.uk> parents: 1 diff changeset	27 print "Max conseq has %d terms, totalling %d" % search(1000000)

Mercurial > hg > euler

annotate problem50.py @ 14:49c96972949d default tip