A dumb question about a class

[Dick Moores]

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
<http://aspn.activestat e.com/ASPN/Cookbook/Python/Recipe/523048>.

Thanks,

Dick Moores

=============== =============== =============== ========
class PrimeList:
def __init__(self, initial=0):
self.primelist = [2,3]
self.primelooku p = [0,0,1,1]
self.max_prime = 3
self.grow_prime list(initial)

def grow_primelist( self,number):
newprimes = []
while self.max_prime <= number:
next = self.nextprime( )
newprimes.appen d(next)
self.max_prime = next
size_difference = self.max_prime - len(self.primel ookup) + 1
self.primelooku p.extend([0] * size_difference )
for i in newprimes:
self.primelooku p[i]=1

def contains(self,n umber):
if number < 2:
return 0
if number len(self.primel ookup) - 1:
self.grow_prime list(number)
return self.primelooku p[number]
return self.primelooku p[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)
=============== =============== =============== =========

[Steven Bethard]

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
<http://aspn.activestat e.com/ASPN/Cookbook/Python/Recipe/523048>.

The short answer is that use should look something like::

>>plist = PrimeList()
plist.contain s(32)

False

>>plist.contain s(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.ifilt er(prime.__rmod __, numbers)
class PrimeList(objec t):
def __init__(self):
# infinite iterator of primes
self._prime_ite r = iter_primes()

# the last prime we've seen
self._last_prim e = 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__(se lf, n):
# add primes to the list until we exceed n
while n self._last_prim e:
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_prim e = self._prime_ite r.next()
self._prime_set .add(self._last _prime)
STeVe

[Dick Moores]

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.ifilt er(prime.__rmod __, numbers)
class PrimeList(objec t):
def __init__(self):
# infinite iterator of primes
self._prime_ite r = iter_primes()

# the last prime we've seen
self._last_prim e = 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__(se lf, n):
# add primes to the list until we exceed n
while n self._last_prim e:
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_prim e = self._prime_ite r.next()
self._prime_set .add(self._last _prime)

I'm afraid my next question is "How do I run this"?

Dick

[Steven Bethard]

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.ifilt er(prime.__rmod __, numbers)
class PrimeList(objec t):
def __init__(self):
# infinite iterator of primes
self._prime_ite r = iter_primes()

# the last prime we've seen
self._last_prim e = 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__(se lf, n):
# add primes to the list until we exceed n
while n self._last_prim e:
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_prim e = self._prime_ite r.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

[Dick Moores]

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::

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.ifilt er(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(p rime)
=============== =============== ==============

Thanks for your help. I didn't learn much about classes, but
appreciated your iter_primes() a lot!

Dick Moores

[Dustan]

On Aug 12, 5:09 pm, Steven Bethard <steven.beth... @gmail.comwrote :

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.ifilt er(prime.__rmod __, numbers)

This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient for larger numbers (millions or billions, or even bigger)?

[Dustan]

On Aug 12, 7:35 pm, Dustan <DustanGro...@g mail.comwrote:

On Aug 12, 5:09 pm, Steven Bethard <steven.beth... @gmail.comwrote :

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.ifilt er(prime.__rmod __, numbers)

This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient 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?

[Steven Bethard]

Dustan wrote:

On Aug 12, 7:35 pm, Dustan <DustanGro...@g mail.comwrote:

>On Aug 12, 5:09 pm, Steven Bethard <steven.beth... @gmail.comwrote :

>> 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.ifilt er(prime.__rmod __, numbers)

This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient 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

[Steven Bethard]

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::

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

[Steven Bethard]

Steven Bethard wrote:

Dustan wrote:

>On Aug 12, 7:35 pm, Dustan <DustanGro...@g mail.comwrote:

>>On Aug 12, 5:09 pm, Steven Bethard <steven.beth... @gmail.comwrote :

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.ifilt er(prime.__rmod __, numbers)
This is kind of OT (from the thread), but in this iter_primes
function, numbers is becoming an ifilter of an ifilter of an ifilter
of an ifilter of an ifilter of an ifilter of... Is that really at all
efficient 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.

Ok, I played around with it myself. Here are the two implementations I
tested::

def iter_primes_rec ursive():
# 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.ifilt er(prime.__rmod __, numbers)
def iter_primes_map ping():

# mapping from composite number to first prime that revealed
# that number as a composite
composite_to_fa ctor_map = {}

# generate primes forever
for i in itertools.count (2):

# find a factor of the number
factor = composite_to_fa ctor_map.pop(i, None)

# if no factor is found, the number is prime
if factor is None:
yield i
composite_to_fa ctor_map[i * i] = i

# add the factor to the number until we find a new
# composite number
else:
composite = i + factor
while composite in composite_to_fa ctor_map:
composite += factor
composite_to_fa ctor_map[composite] = factor

And here are some timeit results::

$ python -m timeit -s "from script import iter_primes_rec ursive as
iter_primes" "for i in iter_primes():" " if i >= 100:"
" break"
10000 loops, best of 3: 102 usec per loop

$ python -m timeit -s "from script import iter_primes_map ping 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_rec ursive 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_map ping 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