Generators/iterators, Pythonicity, and primes

[Scott David Daniels]

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