Steven D'Aprano wrote:
On Sun, 05 Apr 2009 00:28:17 -0400, Miles wrote:
def prime_gen(): ...
That's pretty sweet, but we can make it even faster. We can speed things
up by incrementing by two instead of one, to avoid pointlessly testing
even numbers that we know must fail. We can also speed things up a tad by
making the common test first, and by storing squares rather than
recalculating them each time through the loop.
Much as I had done independently
def prime_gen2():
yield 2
n = 3
yield n
prime_list = [(2, 4), (3, 9)]
it = itertools.count(4)
for n in it:
n = it.next()
for p,p2 in prime_list:
if n % p == 0:
break
elif p2 > n:
prime_list.append((n, n*n))
yield n
break
else:
raise RuntimeError("Shouldn't have run out of primes!")
Here is another speedup (from my prime pair hunt days):
Check only 2 of every 6 integers.
[6N + 0, 6N + 2, 6N + 4] are divisible by 2, [6N + 0, 6N + 3] by 3.
def prime_gen3():
check_list = [(5, 25)]
yield 2
yield 3
yield 5
n = 5
for incr in itertools.cycle((2, 4)):
n += incr
for p, p_squared in check_list:
if p_squared > n:
check_list.append((n, n * n))
yield n
break
elif n % p == 0:
break
else:
raise Exception("Shouldn't have run out of primes!")
--Scott David Daniels
scott.dani...@acm.org
--
http://mail.python.org/mailman/listinfo/python-list
