[Tutor] More primes play
Kirby Urner
urnerk@qwest.net
Thu, 31 Jan 2002 19:36:39 -0800
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