import repository from arizona
[raven.git] / tools / phonehome / sieve.py
1 from __future__ import generators
2
3 def eratosthenes():
4         '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''\r
5         D = {}  # map composite integers to primes witnessing their compositeness\r
6         q = 2   # first integer to test for primality\r
7         while 1:\r
8                 if q not in D:\r
9                         yield q        # not marked composite, must be prime\r
10                         D[q*q] = [q]   # first multiple of q not already marked\r
11                 else:\r
12                         for p in D[q]: # move each witness to its next multiple\r
13                                 D.setdefault(p+q,[]).append(p)\r
14                         del D[q]       # no longer need D[q], free memory\r
15                 q += 1\r
16 \r
17
18