That cofactor would have to have a prime factor less than sqrt(n). On Tuesday, July 2, 2013, Greg Ewing wrote:
Oscar Benjamin wrote:
def primes(): primes_seen = [] for n in count(2): if all(n % p for p in primes_seen): yield n primes_seen.append(n)
This algorithm is actually even poorer as it doesn't stop at sqrt(n).
Nor should it! When you're only dividing by primes, you can't stop at sqrt(n), you have to divide by *all* the primes less than n. Otherise you could miss a prime factor greater than sqrt(n) whose cofactor is not prime.
(Not relevant to the original disussion, I know, but my inner mathematician couldn't restrain himself.)
-- Greg ______________________________**_________________ Python-ideas mailing list Python-ideas@python.org http://mail.python.org/**mailman/listinfo/python-ideas<http://mail.python.org/mailman/listinfo/python-ideas>