Mercurial > hg > euler
changeset 7:ba09b2802674
Primes library
author | Dominic Cleal <dominic@computerkb.co.uk> |
---|---|
date | Mon, 01 Dec 2008 12:44:57 +0000 |
parents | 521bd734e291 |
children | ca8801ad08e9 |
files | primes.py |
diffstat | 1 files changed, 42 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/primes.py Mon Dec 01 12:44:57 2008 +0000 @@ -0,0 +1,42 @@ +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 +