# 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