Geek Answers Handbook

Lazy Sieve of Eratoshenes in Python

I am trying to code the lazy version of Sieve of Eratosthenes in Python 3.2. Here is the code:

import itertools
def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        yield prime

However, when I iterate over prime numbers (), I get only consecutive numbers. For instance.

print(list(itertools.islice(primes(),0,10)))

prints a list

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

To my surprise, the following tiny modification to primes () makes it work:

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = (i for i in candidates if i % prime)
        next(itertools.tee(candidates)[1]) ########### NEW LINE
        yield prime

I assume that I have something missing in the generator parameter area

candidates = (i for i in candidates if i % prime)

but I don’t see how to fix the code without adding this random new line. Does anyone know what I'm doing wrong? Thank.

+5
source share
3 answers

The fix should really replace:

candidates = (i for i in candidates if i % prime)

with:

candidates = (lambda prime: (i for i in candidates if i % prime))(prime)
+6
source

, /, :

def filter_multiples(n, xs):
    for i in xs:
        if i % n
            yield i

def primes():
    candidates = itertools.count(2)
    while True:
        prime = next(candidates)
        candidates = filter_multiples(prime, candidates)
        yield prime

( Pytho , , ...)

, , , Erastothenes. , : http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

+1

Here's a Python implementation of a genuine haskell-based primary sieve in a document: Genuine Eratosthenes sieve Melissa E. O'Neill

It does not use recursion or trial division, but is rather hungry.

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: yield p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p,n,o,p))
    yield p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p,n,o,p))
            yield p
            continue
        while t[0][0] <= p:
            _,b,c,d = t[0]
            heapreplace(t, (b*d,b+w[c],(c+1)%l,d))

Following:

import itertools
print list(itertools.islice(sieve(),0,10))

prints:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+1
source

More articles:


All Articles