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