On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <span dir="ltr">&lt;<a href="mailto:gregor.lingl@aon.at">gregor.lingl@aon.at</a>&gt;</span> wrote:<br><div class="gmail_quote"><div>&nbsp;</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Michel Paul&#39;s code:<div class="Ih2E3d"><br>
<br>
def primes():<br>
 &nbsp; sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway<br>
 &nbsp; yield sofar[0] # get these out of the way<br>
 &nbsp; yield sofar[1] # the only even prime<br>
 &nbsp; yield sofar[2] # and then 3<br>
 &nbsp; candidate = 5 # we&#39;ll increment from here on<br>
 &nbsp; while True: # go forever<br>
 &nbsp; &nbsp; &nbsp; for factor in sofar[1:]: # skip -1 (or don&#39;t use it in the first place)<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if factor ** 2 &gt; candidate: &nbsp;# did we pass?<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield candidate # woo hoo!<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sofar.append(candidate) # keep the gold<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp;# onward!<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if not candidate % factor: # oops, no remainder<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break &nbsp;# this is a composite<br>
 &nbsp; &nbsp; &nbsp; candidate += 2 # next odd number please<br>
<br></div>
Time: &nbsp; &nbsp;100000: &nbsp;1.58 s &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;500000: &nbsp;32.25 s<br>
-----</blockquote><div><br>Actually, that&#39;s Kirby&#39;s code.<br>This is what I sent:<br><br>def primes():<br>&nbsp;&nbsp;&nbsp; p = [-1, 2, 3]<br>&nbsp;&nbsp;&nbsp; for x in p: yield x<br>
&nbsp;&nbsp;&nbsp; def is_prime(n):<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; for factor in p[1:]:<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if factor**2 &gt; n: return True<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if n%factor == 0: return False<br>&nbsp;&nbsp;&nbsp; multiple = 6<br>&nbsp;&nbsp;&nbsp; while True:<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if is_prime(multiple-1): yield multiple-1; p.append(multiple-1)<br>

&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1)<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; multiple += 6<br><font color="#888888"><br></font>Is this what was tested?&nbsp; Or what was listed?&nbsp; Just curious.<br>&nbsp;</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I&#39;ve modified this one slightly, with a surprising effect<br>
(I conjecture mainly due to avoiding copying p repeatedly):<br>
<br>
def primes():<br>
 &nbsp; yield(-1)<br>
 &nbsp; p = [2, 3]<div class="Ih2E3d"><br>
 &nbsp; for x in p: yield x<br>
 &nbsp; def is_prime(n):<br></div>
 &nbsp; &nbsp; &nbsp; for factor in p:<div class="Ih2E3d"><br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if factor**2 &gt; n: return True<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if n%factor == 0: return False<br>
 &nbsp; multiple = 6<br>
 &nbsp; while True:<br></div>
 &nbsp; &nbsp; &nbsp; for cand in multiple-1, multiple+1:<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if is_prime(cand):<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield cand<br>
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p.append(cand)<br>
 &nbsp; &nbsp; &nbsp; multiple += 6<br>
<br>
Time: &nbsp; &nbsp;100000: &nbsp;0.14 s &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;500000: &nbsp;1.05 s<br>
-----<br>
<br>
</blockquote></div><br>Yeah, I like the &#39;for cand in multiple-1, multiple+1&#39;.&nbsp; I actually did do it that way on a previous occasion.&nbsp; So this is very interesting.<br><br>- Michel<br>