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

[michel paul]

On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <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.


> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20090118/f4fb678d/attachment.htm>