Mercurial > hg > euler
view primes.py @ 7:ba09b2802674
Primes library
author | Dominic Cleal <dominic@computerkb.co.uk> |
---|---|
date | Mon, 01 Dec 2008 12:44:57 +0000 |
parents | |
children | ca8801ad08e9 |
line wrap: on
line source
import math class sieve: def sieve(self): '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.''' D = {} # map composite integers to primes witnessing their compositeness q = 2 # first integer to test for primality while 1: if q not in D: yield q # not marked composite, must be prime D[q*q] = [q] # first multiple of q not already marked else: for p in D[q]: # move each witness to its next multiple D.setdefault(p+q,[]).append(p) del D[q] # no longer need D[q], free memory q += 1 class test: cache = { } def __isprime(self, x): for t in range(2, int(math.floor(math.sqrt(x))) + 1): if x % t == 0: return False return True def __add(self, x, p): self.cache[x] = p def isprime(self, x): if x in self.cache: return self.cache[x] r = self.__isprime(x) self.cache[x] = r return r class testsieve(test, sieve): def sieve(self): for p in sieve.sieve(): test.__add(p, True) yield p