Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #50366
| Newsgroups | comp.lang.python |
|---|---|
| Date | 2013-07-10 08:47 -0700 |
| References | <mailman.4522.1373464867.3114.python-list@python.org> <15167633-b6e7-46cc-a043-8dfe8aaad11e@googlegroups.com> <mailman.4525.1373469147.3114.python-list@python.org> |
| Message-ID | <ff09d214-1962-4500-a2a3-483872ce2cb9@googlegroups.com> (permalink) |
| Subject | Re: Prime number generator |
| From | bas <blswinkels@gmail.com> |
On Wednesday, July 10, 2013 5:12:19 PM UTC+2, Chris Angelico wrote: > Well, that does answer the question. Unfortunately the use of lambda > there has a severe performance cost [ ...] If you care about speed, you might want to check the heapq module. Removing the smallest item and inserting a new item in a heap both cost O(log(N)) time, while finding the minimum in a dictionary requires iterating over the whole dictionary, which cost O(N) time. (untested) #before loop from heapq import * primes = [(2,2)] #heap of tuples (multiple, prime). start with 1 item, so no need for heapify #during loop smallest, prm = heappop(primes) heappush(primes, (smallest+prm, prm)) #when new prime found heappush(primes, (i+i, i)) > > Still trying to figure out your algorithm ... > It's pretty simple. [...] I understand what you are trying, but it is not immediately clear to me that it works correctly if for example a smallest factor appears twice in the list. I don't have time for it now, but it for sure can be simplified. The while loop, for example, can be replaced by an if, since it will never execute more than once (since if i is prime > 2, i+1 will be divisible by 2)
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 00:00 +1000
Re: Prime number generator Bas <wegwerp@gmail.com> - 2013-07-10 07:35 -0700
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 01:12 +1000
Re: Prime number generator bas <blswinkels@gmail.com> - 2013-07-10 08:47 -0700
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:15 +1000
Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 18:47 +0100
Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-10 12:56 -0600
Re: Prime number generator Joshua Landau <joshua@landau.ws> - 2013-07-10 20:06 +0100
Re: Prime number generator bryanjugglercryptographer@yahoo.com - 2013-07-30 21:57 -0700
Re: Prime number generator Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-10 16:01 +0000
Re: Prime number generator Chris Angelico <rosuav@gmail.com> - 2013-07-11 02:52 +1000
Re: Prime number generator albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-07-30 10:58 +0000
Re: Prime number generator Ian Kelly <ian.g.kelly@gmail.com> - 2013-07-30 11:33 -0600
csiph-web