A dumb question about a class

[thattommyhallll@gmail.com]

On Aug 13, 3:30 am, Steven Bethard <steven.beth... at gmail.com> wrote:
> Dick Moores wrote:
> > At 03:35 PM 8/12/2007, Steven Bethard wrote:
> >> Note that if you just want to iterate over all the primes, there's no
> >> need for the class at all.  Simply write::
>
> >>      forprimein iter_primes():
>
> > Even if I want to test only 1 integer, or want the list of primes in a
> > certain interval, I don't need the class at all
>
> Yep.  That was the basis of my original feeling that the recipe was
> kinda overkill.
>
> > Thanks for your help. I didn't learn much about classes, but appreciated
> > your iter_primes() a lot!
>
> You're welcome, though I can't actually take credit for iter_primes().
> The original version is due to Tim Hochberg, in a comment on this recipe:
>
>      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117119
>
> FWIW, he says that he "managed to generate all primes up to 909,691
> before it bombed the Python interpreter mysteriously, but it takes a while!"
>
> I'm not particularly married to thatprimegenerator. For your purposes,
> any generator version of iter_primes() is probably more useful than the
> class you were looking at. You can see some other implementations ofprimegenerators on that same recipe page.
>
> STeVe

I wrote that recipe, did not realise anyone was using it (I forgot to
update it with the version I now use)
I thought any prime generator is not a good idea for the following
reasons:
   You end up carrying around a list of primes anyway,
   It is not faster than the Sieve of Eratosthenes

Here is the latest version (following Steves lead doing __contains__ ,
thanks Steve)
(I held off doing this as I had not properly implemented _isprime , it
returned incorrect values if you asked it about very big numbers, now
it will bruteforce an answer)

It is slower than Steves unless you use Psyco, then its two times as
fast.
I was surprised as I had used generators and had slower time, but was
unfamiliar with ifilter (but will be playing with it soon) - that may
give the speedup

Also, does anyone know if there is some magic that makes
i in some_set
loads faster than
i in some_list
as if I tweek Steves to use a list instead, it slows down loads.

All the very best,
Tom

PS: I am about to go to bed, but will post the tests I used etc to my
blog tomorrow.


"""

class PrimeList:
	def __init__(self, initial=0):
		self.primelist = [2]
		self.primelookup = [0,0,1,1]
		self.max_prime = 2
		self.initialise_list(initial)

	def initialise_list(self,upto):
		"Good old Sieve of Eratosthenes"
		if upto <= 3:
			pass
		self.primelookup.extend([0,1] * ((upto-3)//2))
		if upto % 2 == 0:
			self.primelookup.extend([0])
		for i in range(3, upto + 1 , 2):
			if self.primelookup[i]:
				self.primelist.append(i)
				self.max_prime = i
				j = i + i
				while j <= upto:
					self.primelookup[j] = 0
					j += i

	def __contains__(self,number):
		if number < 2:
			return False
		if number > self.max_prime - 1:
			#print "Asking for what I dont have!"
			return self._isprime(number)
		return self.primelookup[number]

	def _isprime(self, number):
		for prime in self.primelist:
			if prime > number ** .5:
				break
			if number % prime == 0:
				return False
		if number < self.max_prime ** 2:
			return True
		else:
			#Brute forcing
			for i in range(self.max_prime,number ** .5 + 1, 2):
				if number % i == 0:
					return False
			return True


"""