<div dir="ltr">On Tue, Jul 2, 2013 at 3:35 PM, Greg Ewing <span dir="ltr"><<a href="mailto:greg.ewing@canterbury.ac.nz" target="_blank">greg.ewing@canterbury.ac.nz</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">Oscar Benjamin wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
def primes():<br>
    primes_seen = []<br>
    for n in count(2):<br>
        if all(n % p for p in primes_seen):<br>
            yield n<br>
            primes_seen.append(n)<br>
<br>
This algorithm is actually even poorer as it doesn't stop at sqrt(n).<br>
</blockquote>
<br></div>
Nor should it! When you're only dividing by primes, you<br>
can't stop at sqrt(n), you have to divide by *all* the<br>
primes less than n. Otherise you could miss a prime<br>
factor greater than sqrt(n) whose cofactor is not prime.<br>
<br>
(Not relevant to the original disussion, I know, but<br>
my inner mathematician couldn't restrain himself.)</blockquote><div><br></div><div style>That would imply that the cofactor has no prime factors (or else you would have hit them), which would mean it must be prime itself (and therefore you hit the cofactor earilier).</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="HOEnZb"><font color="#888888"><br>
<br>
-- <br>
Greg</font></span><div class="HOEnZb"><div class="h5"><br>
______________________________<u></u>_________________<br>
Python-ideas mailing list<br>
<a href="mailto:Python-ideas@python.org" target="_blank">Python-ideas@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/python-ideas" target="_blank">http://mail.python.org/<u></u>mailman/listinfo/python-ideas</a><br>
</div></div></blockquote></div><br></div></div>