michel paul schrieb:
On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <[email protected]
<mailto:[email protected]>> 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
_______________________________________________
Edu-sig mailing list
[email protected]
http://mail.python.org/mailman/listinfo/edu-sig
