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)
================================================== ==== 10 1322
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
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
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
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
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.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)?
On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.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.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 memoryefficiency and the
likes, how do they compare/contrast?
Dustan wrote:
On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.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.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 memoryefficiency 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
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 wrote:
Dustan wrote:
>On Aug 12, 7:35 pm, Dustan <DustanGro...@gmail.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.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 memoryefficiency 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 nonrecursive 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
On Aug 13, 3:30 am, Steven Bethard <steven.beth...@gmail.comwrote:
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] * ((upto3)//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
""" This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Piedro 
last post by:
Hi group,
as I was browsing the web and checking out w3schools.com I read that
the font tag was deprecated and that I should use css styles for
formatting like
for example
<p class="p1">
Text...

by: TGF 
last post by:
How do you copy a String type into a native char buffer? Dumb
question, but not sure how to do it :(
TGF

by: wASP 
last post by:
Hello everyone,
I'm new to C# and ASP.NET, so pardon my stupidity on this one.
I'm having a problem with referencing methods/functions external
to a class member function.
My code is as...

by: dhnriverside 
last post by:
Hi peeps
Ok, so I thought I'd have a go at making a console app in VS2k5... I haven't
written any windows apps for years, let alone dos apps (been web programming)
and I've hit a dumb error...
...

by: Derek Martin 
last post by:
Not like I haven't asked dumb ones before, but I want to take my API that I
designed and create a DLL out of it, instead of it sitting inside my main
form. In VS2K3, how do I go about doing...

by: CMM 
last post by:
Is it me or has anyone noticed that F1 is really dumb in VS2005. Since VB3 I
have been able to click F1 on an ambiguous method in code and the IDE
automatically determines the type based on the...

by: sp 
last post by:
I create an xml file in a text editor:
<?xml version="1.0" encoding="utf8"?>
<elts>
<elt id="1" class="c1">content1</elt>
<elt id="2" class="c1">content2</elt>
</elts>
Then I load the file...

by: Joel Hedlund 
last post by:
Hi!
There's one thing about dictionaries and __hash__() methods that puzzle me. I
have a class with several data members, one of which is 'name' (a str). I would
like to store several of these...

by: rdufour 
last post by:
Downloaded a sample that is supposed to show how to localize a web site and
started playing with the code, its in Vs2003, so I figure I would take code
and put it in Vs 2005 and doing so use it a...

by: isladogs 
last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
For other local times, please check World Time Buddy
In...

by: jianzs 
last post by:
Introduction
Cloudnative applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...

by: abbasky 
last post by:
### Vandf component communication method one: data sharing
Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...

by: fareedcanada 
last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...

by: egorbl4 
last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это
Что это? Что мне с этим делать?
...

by: MeoLessi9 
last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

by: DolphinDB 
last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation.
Take...

by: DolphinDB 
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion highfrequency records to 61 million...

by: Aftab Ahmad 
last post by:
Hello Experts!
I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
 