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
if you change line 7 to :
you don't need line 9 anymore.
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
Sorry: seive is not correctly formatted.
@Louis @Deiter Thanks for your comment and corrections!
I am afraid that the code of Dieter is an infinite loop.
That is intention. seive is a generator for an infinite list (restricted by system resources) of primes.
A little less infinite...but useful:
this variant is faster.
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: