Welcome, guest | Sign In | My Account | Store | Cart

It's an iterator that returns prime numbers.

Got the idea from here: www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Python, 14 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14``` ```from itertools import count from collections import defaultdict def seive(): table = defaultdict(list) for x in count(2): facts = table[x] if facts: del table[x] for p in facts: table[x+p] = table[x+p] + [p] else: table[x*x] = [x] yield x ```

Louis RIVIERE 13 years, 9 months ago

maybe

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

could be

``````table[x+p].append(p)
``````
Louis RIVIERE 13 years, 9 months ago

if you change line 7 to :

``````facts = table.pop(x, None)
``````

you don't need line 9 anymore.

Dieter Kadelka 13 years, 9 months ago

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

Dieter Kadelka 13 years, 9 months ago

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
``````
Alejandro Peralta (author) 13 years, 9 months ago

@Louis @Deiter Thanks for your comment and corrections!

Thanasis Stamos 13 years, 9 months ago

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

Dieter Kadelka 13 years, 9 months ago

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

Sunjay Varma 13 years, 9 months ago

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
``````
Louis RIVIERE 13 years, 9 months ago

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
``````
Paul Hofstra 12 years, 6 months ago

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
``````
 Created by Alejandro Peralta on Tue, 20 Jul 2010 (MIT)

### Required Modules

• (none specified)