[Tutor] More primes play

[Kirby Urner]

Continuing a thread of playing with prime number listings,
I'm appending a class definition I wrote awhile ago that
creates objects you can slice from, as show below, and
also iterate over, as also shown:

   >>> from play import Primes
   >>> myprimes = Primes()
   >>> myprimes[0:10]
   [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
   >>> myprimes[100]
   547
   >>> myprimes[3]
   7
   >>> for i in myprimes:
  	  print i
	  if i > 2000:  break

It's kind of like getting an object inside of which all
the primes already exist -- which is of course not true.
Through lazy evaluation (or "just in time" supply), it
internally iterates forward, appending new primes to its
internal list, in hopes of satisfying a user request.
But as we all know, trial-by-division (the algorithm
used here) wimps out when the going gets tough.  So
this is mainly for playing with low primes (interpret
as you will what "low" means).

What's efficient about doing this as a class is that
the primes list doesn't go away between uses of the
instances, i.e. if you've computed up to the 100th prime,
and ask for the 200th, it's not going to start over from
scratch -- it'll just keep appending.  Likewise, if you
ask for the 10th prime, but have already computed out to
the 100th, well, then there's no further computation
needed at all.

The whole iterator/generator business is best explored
in 2.2 and above, so yes, this is for you folks who are
at liberty to play with the latest snake:

class Primes:
     """
     Represents open-ended, sequential list of prime numbers
     starting with 2.  Uses trial-by-division generator to append
     to list.  Maintains current pointer, allows random access
     and list slicing syntax (but not from "end of list").
     Given simple trial-by-division, this class is suitable for
     exploring low primes only.
     """
     pr = [2]  # class level list of primes

     def __init__(self):
         self.gen = self.__generator()
         self.current = -1
         self.max = 0

     def __iter__(self):
         """
         this object implements iteration
         """
         return self

     def next(self):
         """
         invoke gen (internal lazy evaluator) only if needed
         """
         self.current += 1
         self.max = max(self.max,self.current)
         if self.current > len(Primes.pr)-1:
             return self.gen.next()
         else:
             return Primes.pr[self.current]

     def previous(self):
         """
         move pointer back one position
         """
         self.current -= 1
         if self.current < 0:
             self.current = 0
         return self.pr[self.current]

     def first(self):
         """
         return to 0th position
         """
         self.current = 0
         return Primes.pr[self.current]

     def last(self):
         """
         jump to highest position ever pointed to
         by this object
         """
         self.current = self.max
         return Primes.pr[self.current]

     def skip(self,n):
         """
         skip n primes (n may be negative, to skip
         backward)
         """
         # pointer must be >= 0
         return self.__getitem__(max(0,self.current + n))

     def __getitem__(self,n):
         """
         implements syntax object[n] for nth prime
         """
         if n<0:  raise ValueError,"Out of range"
         if n > len(Primes.pr)-1:
             self.current = self.max
             while n > self.current:
                 self.next()
         else:
             self.current = n
             self.max = max(self.max,self.current)
         return Primes.pr[self.current]

     def __getslice__(self,a,b):
         rlist = []
         if b==2147483647 or a<0 or b<0:
             raise ValueError("Unbounded above")
         for i in range(a,b):
             rlist.append(self.__getitem__(i))
         return rlist

     def __generator(self):
         """
         Iterator for lazy evaluation.
         Yield next higher prime, accruing successive primes
         in class variable pr (shared by all Prime objects)

         Uses trial-by-division, long integers if necessary
         """
         i = Primes.pr[-1]
         if i==2:
             i -= 1
         new = 0
         while 1:
            try:
                i += 2
            except OverflowError:
                i += 2L
            if new:
                yield Primes.pr[-1]
                new = 0
            for t in Primes.pr:
                if t*t > i:
                    # if t**2>candidate, we have a new prime
                    Primes.pr.append(i)
                    new = 1
                    break
                if i%t == 0:
                    # test divide by primes so far,
                    # move to next odd whenever remainder=0
                    break

Kirby