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 = { 1: False }
	
	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(self):
			test._add(self, p, True)
			yield p