[Edu-sig] Pythonic Math must include...

[Gregor Lingl]

michel paul schrieb:
> On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <gregor.lingl at aon.at 
> <mailto:gregor.lingl at 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.
Sorry. Of course, you are right. That was a copy and paste - error.
Your code was what was tested and the result of which is listed in
the table. And you can easily recognize, that it was also your code,
that I had modified. (see below)

Next time I'll be more careful

Gregor

>  
>
>     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