That cofactor would have to have a prime factor less than sqrt(n).<span></span><br><br>On Tuesday, July 2, 2013, Greg Ewing  wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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>
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.)<br>
<br>
-- <br>
Greg<br>
______________________________<u></u>_________________<br>
Python-ideas mailing list<br>
<a>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>
</blockquote>