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 11 years, 6 months ago

maybe

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

could be

table[x+p].append(p) Louis RIVIERE 11 years, 6 months ago

if you change line 7 to :

facts = table.pop(x, None)

you don't need line 9 anymore. Dieter Kadelka 11 years, 6 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 11 years, 6 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) 11 years, 6 months ago

@Louis @Deiter Thanks for your comment and corrections! Thanasis Stamos 11 years, 6 months ago

I am afraid that the code of Dieter is an infinite loop. Dieter Kadelka 11 years, 6 months ago

That is intention. seive is a generator for an infinite list (restricted by system resources) of primes. Sunjay Varma 11 years, 6 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 11 years, 6 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 10 years, 3 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)