440,928 Members | 1,210 Online Need help? Post your question and get tips & solutions from a community of 440,928 IT Pros & Developers. It's quick & easy.

# A dumb question about a class

 P: n/a I'm still trying to understand classes. I've made some progress, I think, but I don't understand how to use this one. How do I call it, or any of its functions? It's from the Cookbook, at . Thanks, Dick Moores ================================================== === class PrimeList: def __init__(self, initial=0): self.primelist = [2,3] self.primelookup = [0,0,1,1] self.max_prime = 3 self.grow_primelist(initial) def grow_primelist(self,number): newprimes = [] while self.max_prime <= number: next = self.nextprime() newprimes.append(next) self.max_prime = next size_difference = self.max_prime - len(self.primelookup) + 1 self.primelookup.extend( * size_difference) for i in newprimes: self.primelookup[i]=1 def contains(self,number): if number < 2: return 0 if number len(self.primelookup) - 1: self.grow_primelist(number) return self.primelookup[number] return self.primelookup[number] def nextprime(self): i = self.max_prime + 2 while 1: isprime = True for prime in self.primelist: if i % prime == 0: isprime = False i += 2 break if isprime: self.primelist.append(i) return(i) ================================================== ==== Aug 12 '07 #1
10 Replies

 P: n/a Dick Moores wrote: I'm still trying to understand classes. I've made some progress, I think, but I don't understand how to use this one. How do I call it, or any of its functions? It's from the Cookbook, at . The short answer is that use should look something like:: >>plist = PrimeList()plist.contains(32) False >>plist.contains(23) True But this doesn't seem like a particularly good recipe. Seems like you would really rather be writing code like:: >>plist = PrimeList()1 in plist False >>2 in plist True >>22 in plist False >>23 in plist True >>782 in plist False >>787 in plist True Here's how I'd write the recipe:: import itertools def iter_primes(): # an iterator of all numbers between 2 and +infinity numbers = itertools.count(2) # generate primes forever while True: # get the first number from the iterator (always a prime) prime = numbers.next() yield prime # remove all numbers from the (infinite) iterator that are # divisible by the prime we just generated numbers = itertools.ifilter(prime.__rmod__, numbers) class PrimeList(object): def __init__(self): # infinite iterator of primes self._prime_iter = iter_primes() # the last prime we've seen self._last_prime = None # all primes seen so far self._prime_set = set() # add the first prime (so that _last_prime is set) self._add_prime() def __contains__(self, n): # add primes to the list until we exceed n while n self._last_prime: self._add_prime() # return True if n is one of our primes return n in self._prime_set def _add_prime(self): # take a prime off the iterator and update the prime set self._last_prime = self._prime_iter.next() self._prime_set.add(self._last_prime) STeVe Aug 12 '07 #2

 P: n/a At 03:09 PM 8/12/2007, Steven Bethard wrote: >Here's how I'd write the recipe:: import itertools def iter_primes(): # an iterator of all numbers between 2 and +infinity numbers = itertools.count(2) # generate primes forever while True: # get the first number from the iterator (always a prime) prime = numbers.next() yield prime # remove all numbers from the (infinite) iterator that are # divisible by the prime we just generated numbers = itertools.ifilter(prime.__rmod__, numbers) class PrimeList(object): def __init__(self): # infinite iterator of primes self._prime_iter = iter_primes() # the last prime we've seen self._last_prime = None # all primes seen so far self._prime_set = set() # add the first prime (so that _last_prime is set) self._add_prime() def __contains__(self, n): # add primes to the list until we exceed n while n self._last_prime: self._add_prime() # return True if n is one of our primes return n in self._prime_set def _add_prime(self): # take a prime off the iterator and update the prime set self._last_prime = self._prime_iter.next() self._prime_set.add(self._last_prime) I'm afraid my next question is "How do I run this"? Dick Aug 12 '07 #3

 P: n/a Dick Moores wrote: At 03:09 PM 8/12/2007, Steven Bethard wrote: >Here's how I'd write the recipe:: import itertools def iter_primes(): # an iterator of all numbers between 2 and +infinity numbers = itertools.count(2) # generate primes forever while True: # get the first number from the iterator (always a prime) prime = numbers.next() yield prime # remove all numbers from the (infinite) iterator that are # divisible by the prime we just generated numbers = itertools.ifilter(prime.__rmod__, numbers) class PrimeList(object): def __init__(self): # infinite iterator of primes self._prime_iter = iter_primes() # the last prime we've seen self._last_prime = None # all primes seen so far self._prime_set = set() # add the first prime (so that _last_prime is set) self._add_prime() def __contains__(self, n): # add primes to the list until we exceed n while n self._last_prime: self._add_prime() # return True if n is one of our primes return n in self._prime_set def _add_prime(self): # take a prime off the iterator and update the prime set self._last_prime = self._prime_iter.next() self._prime_set.add(self._last_prime) I'm afraid my next question is "How do I run this"? The same way I showed at the top (which you snipped in your reply):: >>plist = PrimeList()1 in plist False >>2 in plist True >>22 in plist False >>23 in plist True >>782 in plist False >>787 in plist True The first line, ``plist = PrimeList()`` creates a PrimeList object and names it ``plist``. You can then check whether a prime is in that PrimeList object much like you might check a normal ``list`` or ``set`` object -- using the ``in`` operator as above. Note that if you just want to iterate over all the primes, there's no need for the class at all. Simply write:: for prime in iter_primes(): ... HTH, STeVe Aug 12 '07 #4

 P: n/a At 03:35 PM 8/12/2007, Steven Bethard wrote: >Note that if you just want to iterate over all the primes, there's noneed for the class at all. Simply write:: for prime in 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: ==================================== import itertools def iter_primes(): # an iterator of all numbers between 2 and +infinity numbers = itertools.count(2) # generate primes forever while True: # get the first number from the iterator (always a prime) prime = numbers.next() yield prime # remove all numbers from the (infinite) iterator that are # divisible by the prime we just generated numbers = itertools.ifilter(prime.__rmod__, numbers) def listPrimes(n,m): """ Returns the list of primes in closed interval [n,m] """ primes = [] for prime in iter_primes(): if prime m: return primes if n <= prime <= m: primes.append(prime) ============================================ Thanks for your help. I didn't learn much about classes, but appreciated your iter_primes() a lot! Dick Moores Aug 13 '07 #5

 P: n/a On Aug 12, 5:09 pm, Steven Bethard

 P: n/a On Aug 12, 7:35 pm, Dustan

 P: n/a Dustan wrote: On Aug 12, 7:35 pm, Dustan On Aug 12, 5:09 pm, Steven Bethard > def iter_primes(): # an iterator of all numbers between 2 and +infinity numbers = itertools.count(2) # generate primes forever while True: # get the first number from the iterator (always a prime) prime = numbers.next() yield prime # remove all numbers from the (infinite) iterator that are # divisible by the prime we just generated numbers = itertools.ifilter(prime.__rmod__, numbers) This is kind of OT (from the thread), but in this iter_primesfunction, numbers is becoming an ifilter of an ifilter of an ifilterof an ifilter of an ifilter of an ifilter of... Is that really at allefficient for larger numbers (millions or billions, or even bigger)? To word my question better: How does this algorithm compare and contrast to maintaining a dictionary or set and iterating through those structures to find out if a number is divisible? All of those algorithms I've described are O(n^2), if I'm not mistaken, but as far as memory-efficiency and the likes, how do they compare/contrast? I don't have the answer off hand, but if anyone wants to report some timeit results or memory consumption here, I'd be interested. STeVe Aug 13 '07 #8

 P: n/a 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 noneed for the class at all. Simply write:: for prime in 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/Coo.../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 that prime generator. 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 of prime generators on that same recipe page. STeVe Aug 13 '07 #9

 P: n/a Steven Bethard wrote: Dustan wrote: >On Aug 12, 7:35 pm, Dustan >On Aug 12, 5:09 pm, Steven Bethard = 100:" " break" 10000 loops, best of 3: 102 usec per loop \$ python -m timeit -s "from script import iter_primes_mapping as iter_primes" "for i in iter_primes():" " if i >= 100:" " break" 10000 loops, best of 3: 75.2 usec per loop \$ python -m timeit -s "from script import iter_primes_recursive as iter_primes" "for i in iter_primes():" " if i >= 10000:" " break" 10 loops, best of 3: 111 msec per loop \$ python -m timeit -s "from script import iter_primes_mapping as iter_primes" "for i in iter_primes():" " if i >= 10000:" " break" 100 loops, best of 3: 8.4 msec per loop So, somewhat unsurprisingly, the non-recursive version is much faster for larger primes. (Someone should check that both my implementations are right -- I only did a couple of spot checks on the output.) STeVe Aug 13 '07 #10

 P: n/a On Aug 13, 3:30 am, Steven Bethard

### This discussion thread is closed

Replies have been disabled for this discussion. 