Generators/iterators, Pythonicity, and primes
Scott David Daniels
Scott.Daniels at Acm.Org
Sun Apr 5 21:08:04 CEST 2009
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.Daniels at Acm.Org
More information about the Python-list
mailing list