# HG changeset patch
# User Dominic Cleal <dominic@computerkb.co.uk>
# Date 1228135497 0
# Node ID ba09b2802674b9226c2feedd8c14d5f42af611d4
# Parent  521bd734e291ddcfc09d38ecdb9717d9253227fe
Primes library

diff -r 521bd734e291 -r ba09b2802674 primes.py
--- /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
+