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.activestate.com/ASPN/Cookbook/Python/Recipe/523048>.

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([0] * 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)
================================================== ====

[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.activestate.com/ASPN/Cookbook/Python/Recipe/523048>.

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

[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.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

[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.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

[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.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

[Dustan]

On Aug 12, 5:09 pm, Steven Bethard <[e-mail]:

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_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 <[e-mail]:

On Aug 12, 5:09 pm, Steven Bethard <[e-mail]:

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_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 <[e-mail]:

>On Aug 12, 5:09 pm, Steven Bethard <[e-mail]:

>> 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_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 <[e-mail]:

>>On Aug 12, 5:09 pm, Steven Bethard <[e-mail]:

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_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_recursive():
# 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 iter_primes_mapping():

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

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

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

# if no factor is found, the number is prime
if factor is None:
yield i
composite_to_factor_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_factor_map:
composite += factor
composite_to_factor_map[composite] = factor

And here are some timeit results::

$ python -m timeit -s "from script import iter_primes_recursive 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_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

[thattommyhallll]

On Aug 13, 3:30 am, Steven Bethard <[e-mail]:

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/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 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
"""