Infinite list of primes! Yay! (Python recipe) by Alejandro Peralta

ActiveState Code (http://code.activestate.com/recipes/577318/)

maybe

table[x+p] = table[x+p] + [p]

could be

table[x+p].append(p)

if you change line 7 to :

facts = table.pop(x, None)

you don't need line 9 anymore.

Even numbers can be omitted. Here is a simple variant:

def seive(): yield 2 table = defaultdict(list) for x in count(3,2): facts = table.pop(x,None) if facts: for p in facts: table[x+2p].append(p) else: table[xx] = [x] yield x

Sorry: seive is not correctly formatted.

def seive():
    yield 2
    table = defaultdict(list)
    for x in count(3,2):
         facts = table.pop(x,None)
         if facts:
             for p in facts:
                 table[x+2*p].append(p)
             else:
                 table[x*x] = [x]
                 yield x

@Louis @Deiter Thanks for your comment and corrections!

I am afraid that the code of Dieter is an infinite loop.

That is intention. seive is a generator for an infinite list (restricted by system resources) of primes.

A little less infinite...but useful:

def seive(depth=200):
    yield 2
    table = defaultdict(list)
    for x in count(3,2):
         facts = table.pop(x,None)
         if facts:
             for p in facts:
                 table[x+2*p].append(p)
         else:
             table[x*x] = [x]
             depth -= 1
             if not depth: return
             yield x

this variant is faster.

import itertools  
def erat2( ):  
    D = {  }  
    yield 2  
    for q in itertools.islice(itertools.count(3), 0, None, 2):  
        p = D.pop(q, None)  
        if p is None:  
            D[q*q] = q  
            yield q  
        else:  
            x = p + q  
            while x in D or not (x&1):  
                x += p  
            D[x] = p

The version below is even faster. As p and q are both odd and x should be odd, we can add 2p to x and skip the test to check if x is odd. In Python 3:

from itertools import count
def erat2():
    D = {}
    yield 2
    for q in count(3, 2):
        p = D.pop(q, None)
        if p is None:
            D[q * q] = q
            yield q
        else:
            pp = 2 * p
            x = pp + q
            while x in D:
                x += pp
            D[x] = p