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

10 comments

Louis RIVIERE 11 years, 4 months ago  # | flag

maybe

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

could be

table[x+p].append(p)
Louis RIVIERE 11 years, 4 months ago  # | flag

if you change line 7 to :

facts = table.pop(x, None)

you don't need line 9 anymore.

Dieter Kadelka 11 years, 4 months ago  # | flag

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, 4 months ago  # | flag

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, 4 months ago  # | flag

@Louis @Deiter Thanks for your comment and corrections!

Thanasis Stamos 11 years, 4 months ago  # | flag

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

Dieter Kadelka 11 years, 4 months ago  # | flag

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

Sunjay Varma 11 years, 4 months ago  # | flag

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, 4 months ago  # | flag

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, 1 month ago  # | flag

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)
Python recipes (4591)
Alejandro Peralta's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks