On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <gregor.li...@aon.at> wrote:
> Michel Paul's code: > > def primes(): > sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway > yield sofar[0] # get these out of the way > yield sofar[1] # the only even prime > yield sofar[2] # and then 3 > candidate = 5 # we'll increment from here on > while True: # go forever > for factor in sofar[1:]: # skip -1 (or don't use it in the first > place) > if factor ** 2 > candidate: # did we pass? > yield candidate # woo hoo! > sofar.append(candidate) # keep the gold > break # onward! > if not candidate % factor: # oops, no remainder > break # this is a composite > candidate += 2 # next odd number please > > Time: 100000: 1.58 s 500000: 32.25 s > ----- Actually, that's Kirby's code. This is what I sent: def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6 Is this what was tested? Or what was listed? Just curious. > I've modified this one slightly, with a surprising effect > (I conjecture mainly due to avoiding copying p repeatedly): > > def primes(): > yield(-1) > p = [2, 3] > for x in p: yield x > def is_prime(n): > for factor in p: > if factor**2 > n: return True > if n%factor == 0: return False > multiple = 6 > while True: > for cand in multiple-1, multiple+1: > if is_prime(cand): > yield cand > p.append(cand) > multiple += 6 > > Time: 100000: 0.14 s 500000: 1.05 s > ----- > > Yeah, I like the 'for cand in multiple-1, multiple+1'. I actually did do it that way on a previous occasion. So this is very interesting. - Michel
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig