nicoekkart
10/31/2013 - 4:40 PM

Generate infinite prime numbers (Sieve of Eratosthenes)

Generate infinite prime numbers (Sieve of Eratosthenes)

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    D = {}
    q = 2
    
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q+=1