Re: Prime number generator
On Tue, Jul 30, 2013 at 4:58 AM, Albert van der Horst alb...@spenarnc.xs4all.nl wrote: Notice that all values from i on are possibly present. So you are better off with a list indexed by forthcoming i's and each item containing a list of primes. What you do then, more or less, is keep track of all dividers of primes to be. This promises to be reasonable efficient. I've done a similar thing in Forth. What do you do when you get up into the billions? It seems inefficient to keep a mostly empty billion-element list hanging around. There is an unpleasant fact about this kind of generators. If you want to go unbounded, you've no choice but remember all primes. If you go bounded, you need to remember 168 up til 1M, say sqrt(limit)/log(limit). This dramatic difference (and the lack of processors) leads one quickly to decide for some upper bound. Actually, take a look at the generator that I posted in this thread, which avoids this. It is unbounded but gets away with only remembering sqrt(N) primes by recursively regenerating the primes already seen as needed. Thus it only uses (2 * N**(1/2) + 4 * N**(1/4) 8 * N**(1/8) + ...) / log(N) extra memory, which I believe is O(sqrt(N)). -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
In article mailman.4522.1373464867.3114.python-l...@python.org,
Chris Angelico ros...@gmail.com wrote:
And now for something completely different.
I knocked together a prime number generator, just for the fun of it,
that works like a Sieve of Eratosthenes but unbounded. It keeps track
of all known primes and the next composite that it will produce -
for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
greater than 13.
Notable in the algorithm is an entire lack of division, or even
multiplication. Everything is done with addition.
So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value? In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary. Secondly, can the while
ismallest... i+=1 loop become a for...range? It's almost asking for
it, but not quite there. Thirdly, is there any sort of half-sane
benchmark that I can compare this code to? And finally, whose wheel
did I reinvent here? What name would this algorithm have?
Notice that all values from i on are possibly present.
So you are better off with a list indexed by forthcoming i's and
each item containing a list of primes. What you do then, more or less,
is keep track of all dividers of primes to be.
This promises to be reasonable efficient.
I've done a similar thing in Forth.
I've also done a slightly different but related parallel program on a
multi-processor Forth machine where each processor takes care of one
prime.
There is an unpleasant fact about this kind of generators.
If you want to go unbounded, you've no choice but remember all
primes. If you go bounded, you need to remember 168 up til 1M,
say sqrt(limit)/log(limit). This dramatic difference (and the lack
of processors) leads one quickly to decide for some upper bound.
Code tested on Python 3.3, would probably run fine on pretty much any
Python that supports yield, though I don't have a Py2.2 to test from
__future__ import generators on!
I had problems with the print statement on a 2 version, fixed easy
enough.
ChrisA
# -- start --
def primes():
Generate an infinite series of prime numbers.
i=2
yield 2
prime={2:2} # Map a prime number to its next composite (but bootstrap
with 2:2)
while True:
# Find the smallest value in prime[] and its key.
# Is there a standard library way to do this??
# (If two values are equal smallest, either can be returned.)
prm=None
for p,val in prime.items():
if prm is None or valsmallest:
prm,smallest=p,val
prime[prm]+=prm
while ismallest:
yield i
prime[i]=i+i
i+=1
if i==smallest: i+=1
gen=primes()
for i in range(30):
print(next(gen),end=\t) # Star Trek?
print()
# -- end --
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spearc.xs4all.nl =n http://home.hccnet.nl/a.w.m.van.der.horst
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
Chris Angelico wrote: Bas wrote: Still trying to figure out your algorithm ... It's pretty simple. (That's a bad start, I know!) Like the Sieve of Eratosthenes, it locates prime numbers, then deems every multiple of them to be composite. Unlike the classic sieve, it does the deem part in parallel. Instead of marking all the multiples of 2 first, then picking three and marking all the multiples of 3, then 5, etc, this function records the fact that it's up to (say) 42 in marking multiples of 2, and then when it comes to check if 43 is prime or not, it moves to the next multiple of 2. This requires memory to store the previously-known primes, similarly to other methods, but needs no multiplication or division. Knuth points to the method, using a priority queue, in exercise 15 of section 5.2.3 of /Sorting and Searching/, and credits it to B. A. Chartres. -- -Bryan -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Wednesday, July 10, 2013 4:00:59 PM UTC+2, Chris Angelico wrote:
[...]
So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value? In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary.
In [1]: prime = {2: 20, 3: 18, 5: 20, 7: 21, 11: 22, 13: 26}
In [2]: smallest_key = min(prime.iteritems(), key=lambda k_v: k_v[1])[0]
In [3]: smallest_key
Out[3]: 3
Still trying to figure out your algorithm ...
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, Jul 11, 2013 at 12:35 AM, Bas wegw...@gmail.com wrote:
On Wednesday, July 10, 2013 4:00:59 PM UTC+2, Chris Angelico wrote:
[...]
So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value? In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary.
In [1]: prime = {2: 20, 3: 18, 5: 20, 7: 21, 11: 22, 13: 26}
In [2]: smallest_key = min(prime.iteritems(), key=lambda k_v: k_v[1])[0]
In [3]: smallest_key
Out[3]: 3
Well, that does answer the question. Unfortunately the use of lambda
there has a severe performance cost (roughly doubles the total run
time, when I ask for the thousandth prime), without majorly improving
readability. I'll bear it in mind if there's a way to make that work
on either readability or performance, but otherwise, I'll stick with
the explicit loop. Thanks anyway!
Still trying to figure out your algorithm ...
It's pretty simple. (That's a bad start, I know!) Like the Sieve of
Eratosthenes, it locates prime numbers, then deems every multiple of
them to be composite. Unlike the classic sieve, it does the deem
part in parallel. Instead of marking all the multiples of 2 first,
then picking three and marking all the multiples of 3, then 5, etc,
this function records the fact that it's up to (say) 42 in marking
multiples of 2, and then when it comes to check if 43 is prime or not,
it moves to the next multiple of 2. This requires memory to store the
previously-known primes, similarly to other methods, but needs no
multiplication or division.
ChrisA
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On 10 July 2013 15:00, Chris Angelico ros...@gmail.com wrote:
And now for something completely different.
I knocked together a prime number generator, just for the fun of it,
that works like a Sieve of Eratosthenes but unbounded. It keeps track
of all known primes and the next composite that it will produce -
for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
greater than 13.
Notable in the algorithm is an entire lack of division, or even
multiplication. Everything is done with addition.
So, a few questions. Firstly, is there a stdlib way to find the key
with the lowest corresponding value?
Of course there is.
In the above map, it would return
3, because 18 is the lowest value in the list. I want to do this with
a single pass over the dictionary. Secondly, can the while
ismallest... i+=1 loop become a for...range?
Of course it can.
It's almost asking for
it, but not quite there. Thirdly, is there any sort of half-sane
benchmark that I can compare this code to?
Of course there is. I have no clue what, though.
And finally, whose wheel
did I reinvent here?
Mine :P. That just proves the algorithm is older still, though. You
also did it much more neatly and much more slowly, though. The trick
is to avoid that repeated effort of finding the minimum in the dict by
just keeping a sorted list.
I've mocked that up just now:
# Faster code #
from blist import sortedlist
def generate_primes():
primes = sortedlist()
primes.add([4, 2])
yield 2
i = 3
while True:
next_nonprime, prime_factor = primes.pop(0)
for prime in range(i, next_nonprime):
yield prime
primes.add([prime*2, prime])
i = next_nonprime + 1
primes.add([next_nonprime + prime_factor, prime_factor])
# No longer code #
What name would this algorithm have?
I'll call it the flamingo.
Code tested on Python 3.3, would probably run fine on pretty much any
Python that supports yield, though I don't have a Py2.2 to test from
__future__ import generators on!
ChrisA
# -- start --
def generate_primes():
Generate an infinite series of prime numbers.
i = 2
yield 2
primes = {2:2} # Map a prime number to its next composite (but
bootstrap with 2:2)
while True:
prm = min(primes, key=primes.__getitem__)
smallest = primes[prm]
primes[prm] += prm
for prm in range(i, smallest):
yield prm
primes[i] = 2*i
i = smallest + 1
gen=generate_primes()
for i in range(30):
print(next(gen),end=\t) # Star Trek?
print()
# -- end --
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
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) -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, Jul 11, 2013 at 1:43 AM, Joshua Landau jos...@landau.ws wrote:
So, a few questions. Firstly, is there...
Of course there is.
Secondly, can the...
Of course it can.
Thirdly, is there...
Of course there is. I have no clue what, though.
Heh, I guess I was asking for that kind of response :)
The trick
is to avoid that repeated effort of finding the minimum in the dict by
just keeping a sorted list.
I've mocked that up just now:
# Faster code #
from blist import sortedlist
Hmm, blist isn't part of the standard library, so I'd have to hunt
that down. Presumably it's on PyPI.
What name would this algorithm have?
I'll call it the flamingo.
Guess that's as good a name as any!
def generate_primes():
Generate an infinite series of prime numbers.
i = 2
yield 2
primes = {2:2} # Map a prime number to its next composite (but
bootstrap with 2:2)
while True:
prm = min(primes, key=primes.__getitem__)
smallest = primes[prm]
primes[prm] += prm
for prm in range(i, smallest):
yield prm
primes[i] = 2*i
i = smallest + 1
gen=generate_primes()
for i in range(30):
print(next(gen),end=\t) # Star Trek?
print()
And once again, a version that's slower than the original. This one
does at least have the advantage of readability, though, and it's only
a little slower, so I'd say this is the current winner. I would still
replace 2*i with i+i for the sake of boasting no multiplication,
though :)
In terms of the one pass criterion I put on the find-smallest
algorithm, I had been seeking to avoid anything that involved constant
lookups into primes[]. But this solution does look very clean and
simple. I think.
ChrisA
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote: And now for something completely different. I knocked together a prime number generator, just for the fun of it, that works like a Sieve of Eratosthenes but unbounded. [...] So, a few questions. Firstly, is there a stdlib way to find the key with the lowest corresponding value? In the above map, it would return 3, because 18 is the lowest value in the list. Not from a dict, but with a list you would probably use the bisect module. I want to do this with a single pass over the dictionary. Secondly, can the while ismallest... i+=1 loop become a for...range? It's almost asking for it, but not quite there. Thirdly, is there any sort of half-sane benchmark that I can compare this code to? And finally, whose wheel did I reinvent here? What name would this algorithm have? I can't directly answer that question, but I can make a shameless plug for this: https://pypi.python.org/pypi/pyprimes If your prime generator performs better than, or worse than, all of those in the above module, I may have to steal it from you :-) -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Wed, Jul 10, 2013 at 8:00 AM, Chris Angelico ros...@gmail.com wrote:
And now for something completely different.
I knocked together a prime number generator, just for the fun of it,
that works like a Sieve of Eratosthenes but unbounded. It keeps track
of all known primes and the next composite that it will produce -
for instance, after yielding 13, the prime map will be {2: 20, 3: 18,
5: 20, 7: 21, 11: 22, 13: 26}, each one mapped to the first multiple
greater than 13.
Cool! I have a similar generator, and instead of mapping primes to
next composites, it maps next composites to lists of primes. It works
using increment-by-2 and checking the dictionary rather than searching
for the min of the dictionary. You could though adapt that data
structure and just use min(prime) to find the next composite (although
as somebody else noted, a heap would probably be more efficient).
The other interesting thing about my sieve is that it's a recursive
generator. I'll dig it up later and share it.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, Jul 11, 2013 at 1:47 AM, bas blswink...@gmail.com wrote: 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. Ehh, speed isn't the ultimate. I was just trying to avoid something that worked out ridiculously slow (a Python function call IS quite slow). I haven't profiled the code to find out where the bulk of the time is spent, but switching in the lambda-based version doubled total run time, so I didn't like it :) (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)) Ahh, that's the bit I should have thought of! Of course. My original thought experiment had involved basically a really long list, like the classic Sieve but getting longer as time moves on, with composites replaced by None and primes with their next-markers, which I then collapsed to a dict. Always I was thinking in terms of indexing with the prime to get its next composite. Here's the code involving heapq: # -- start -- def primes(): Generate an infinite series of prime numbers. from heapq import heappush,heappop i=2 yield 2 prime=[(2,2)] # Heap while True: smallest, prm = heappop(prime) heappush(prime, (smallest+prm, prm)) while ismallest: yield i heappush(prime, (i+i, i)) i+=1 if i==smallest: i+=1 gen=primes() print([next(gen) for i in range(10)]) for i in range(1000): next(gen) # Star Trek? print(The next prime number is:,next(gen)) # -- end -- And that's significantly shorter, clearer, AND faster than the original. Thanks! 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) Ah, good point. Again, I originally was starting from 1, so the while loop was necessary to catch 2 and 3 in the first run. When I changed it to start at 2 and explicitly yield it first, I didn't notice to change that. It works correctly with the smallest multiple appearing twice because it won't yield primes until the smallest value is higher than the current next-prime. So when it's just yielded 11, for instance, both the 2 and 3 slots hold 12; advancing one of those does nothing, advancing the other allows the bottom loop to notice that 13 is now lower than the minimum value (which will then be 14). ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, Jul 11, 2013 at 2:01 AM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: On Thu, 11 Jul 2013 00:00:59 +1000, Chris Angelico wrote: Thirdly, is there any sort of half-sane benchmark that I can compare this code to? And finally, whose wheel did I reinvent here? What name would this algorithm have? I can't directly answer that question, but I can make a shameless plug for this: https://pypi.python.org/pypi/pyprimes If your prime generator performs better than, or worse than, all of those in the above module, I may have to steal it from you :-) Ha, that's what I was hoping for. My algorithm outperforms several of yours! Look! Rosuav: 0.10868923284942639 awful_primes: 16.55546780386893 naive_primes1: 2.6105180965737276 naive_primes2: 1.358270674066116 trial_division: 0.06926075800136644 turner: 0.5736550315752424 croft: 0.007141969160883832 sieve: 0.01786707528470899 cookbook: 0.014790147909859996 wheel: 0.015050236831779529 Okay, so I outperform only algorithms listed as toys... :| Here's similar figures, going to a higher cutoff (I kept it low for the sake of awful_primes) and using only the algos designed for real use: Rosuav: 2.1318494389650082 croft: 0.11628042111497416 sieve: 0.26868582459502566 cookbook: 0.21551174800149164 wheel: 0.4761577239565362 I didn't seriously think that this would outperform mathematically proven and efficient algorithms, it was just a toy. But at least now I know: It's roughly 20 times slower than a leading algo. And that's after the bas-suggested improvement of using a heap. But hey. If you want the code, you're welcome to it - same with anyone else. Here's the heap version as used in the above timings. MIT license. def primes(): Generate an infinite series of prime numbers. from heapq import heappush,heappop i=2 yield 2 prime=[(2,2)] # Heap while True: smallest, prm = heappop(prime) heappush(prime, (smallest+prm, prm)) if ismallest: yield i heappush(prime, (i+i, i)) i+=1 if i==smallest: i+=1 # Enjoy! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Wed, Jul 10, 2013 at 10:16 AM, Ian Kelly ian.g.ke...@gmail.com wrote: The other interesting thing about my sieve is that it's a recursive generator. I'll dig it up later and share it. As promised. Apologies for the excessive commenting. As noted, this implementation is a recursive generator, which is done so that the primes in the sieve can go only up to the square root of the current prime, rather than tossing in every prime seen so far. from collections import defaultdict from itertools import count, islice def primes(): yield 2 # Set up the data structures. multiples implements the sieve as a dict # that marks upcoming composite numbers and records the prime factors # that disqualified them. multiples = defaultdict(list) # subgen is a recursive sub-generator that supplies prime factors to be fed # into the sieve. islice is used to skip 2 (since we only consider odd # numbers) and 3 (since we can't get it from subgen before we've yielded it # below). subgen = islice(primes(), 2, None) # Initialize the sieve with the first prime factor q. q = 3 # When we reach threshold (the square of the last prime added to the sieve), # it's time to add another prime to the sieve. By construction, threshold # is always an odd composite. threshold = q * q multiples[threshold].append(q + q) # The main loop tries every odd integer, starting with 3. for p in count(3, 2): if p in multiples: # p is composite. Discard the entry from multiples and mark the # next odd multiple of each prime factor that disqualified p. # Because the multiples dict actually stores the doubles of the # prime factors, they need only be added once to get to the next # odd multiple. for q in multiples[p]: multiples[p + q].append(q) del multiples[p] if p == threshold: # All primes up to the previous q ** 2 have been generated. # Get the next prime factor q and add it to the sieve. q = subgen.next() threshold = q * q multiples[threshold].append(q + q) else: # p is prime. Yay! yield p -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Thu, Jul 11, 2013 at 2:54 AM, Ian Kelly ian.g.ke...@gmail.com wrote: As promised. Apologies for the excessive commenting. As noted, this implementation is a recursive generator, which is done so that the primes in the sieve can go only up to the square root of the current prime, rather than tossing in every prime seen so far. Nice. Comes in at 0.23369310904039478 in my oh-so-scientific benchmarking, so it's comparable to several of Steven's algorithms. Runs on Python 3.3 with just the tiny tweak of converting iter.next() to next(iter). ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On 10 July 2013 17:15, Chris Angelico ros...@gmail.com wrote: On Thu, Jul 11, 2013 at 1:47 AM, bas blswink...@gmail.com wrote: 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. Actually, because it's a list under the hood I'd imagine push and pop still take O(n) time :/. Ehh, speed isn't the ultimate. I was just trying to avoid something that worked out ridiculously slow (a Python function call IS quite slow). I haven't profiled the code to find out where the bulk of the time is spent, but switching in the lambda-based version doubled total run time, so I didn't like it :) (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)) Ahh, that's the bit I should have thought of! Of course. My original thought experiment had involved basically a really long list, like the classic Sieve but getting longer as time moves on, with composites replaced by None and primes with their next-markers, which I then collapsed to a dict. Always I was thinking in terms of indexing with the prime to get its next composite. Here's the code involving heapq: # -- start -- def primes(): Generate an infinite series of prime numbers. from heapq import heappush,heappop i=2 yield 2 prime=[(2,2)] # Heap while True: smallest, prm = heappop(prime) heappush(prime, (smallest+prm, prm)) while ismallest: yield i heappush(prime, (i+i, i)) i+=1 if i==smallest: i+=1 gen=primes() print([next(gen) for i in range(10)]) for i in range(1000): next(gen) # Star Trek? print(The next prime number is:,next(gen)) # -- end -- And that's significantly shorter, clearer, AND faster than the original. Thanks! AFAICT, that's exactly my code but using a less-efficient storage medium and a *much* more efficient sorting mechanism. It'd be interesting what could happen if heapq didn't reject blists -- they have better efficiency for changing list sizes (which this code does a lot of). Thanks for the heads-up on heapq, by the way -- it's new to me and a blimmin' good idea. PS: It's faster to use heapreplace(...) than heappop(...);heappush(...) but it only saves a few %. -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau jos...@landau.ws wrote: 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. Actually, because it's a list under the hood I'd imagine push and pop still take O(n) time :/. It shouldn't. You can implement push by appending the new item and then getting it into the right place by performing O(log n) swaps. Likewise for pop, you can update the heap with O(log n) swaps and then removing the tail element. Appending or removing the tail element of a list is amortized O(1). PS: It's faster to use heapreplace(...) than heappop(...);heappush(...) but it only saves a few %. The problem with heapreplace here is that the value to be pushed is dependent on the value returned by pop. -- http://mail.python.org/mailman/listinfo/python-list
Re: Prime number generator
On 10 July 2013 19:56, Ian Kelly ian.g.ke...@gmail.com wrote: On Wed, Jul 10, 2013 at 11:47 AM, Joshua Landau jos...@landau.ws wrote: 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. Actually, because it's a list under the hood I'd imagine push and pop still take O(n) time :/. It shouldn't. You can implement push by appending the new item and then getting it into the right place by performing O(log n) swaps. Likewise for pop, you can update the heap with O(log n) swaps and then removing the tail element. Appending or removing the tail element of a list is amortized O(1). Genius. Bas replied off-list that it won't matter too much anyway as they're over-allocated, but this makes tons of sense. PS: It's faster to use heapreplace(...) than heappop(...);heappush(...) but it only saves a few %. The problem with heapreplace here is that the value to be pushed is dependent on the value returned by pop. That's fine because indexing is much faster than pop. The few % was a real statistic from working, timed code. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
lostinpython wrote: What civil engineers need with all this programming is beyond me. We have to learn another language to program our CADD software, which I find much easier than this. According to my experience, almost every engineer - civil or not - uses programming at least occationally. So every engineering education program should involve at least some programming. /Mikael Olofsson Universitetslektor (Senior Lecturer [BrE], Associate Professor [AmE]) Linköpings universitet --- E-Mail: [EMAIL PROTECTED] WWW: http://www.dtr.isy.liu.se/en/staff/mikael Phone: +46 - (0)13 - 28 1343 Telefax: +46 - (0)13 - 28 1339 --- Linköpings kammarkör: www.kammarkoren.com Vi söker tenorer och basar! -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
In article [EMAIL PROTECTED], lostinpython [EMAIL PROTECTED] wrote: It is a homework assignment from a book but not for a class. I'm trying to teach my self some basic programming before I have to take it in college. If I show enough understanding of the subject, my advisor will let me forgo Intro. to Programming and go into Intro. to C++. What civil engineers need with all this programming is beyond me. We have to learn another language to program our CADD software, which I find much easier than this. But needless to say, I'm stumped on this . . . What's the crack about first place being a paid weekend vacation in Philadelpha, and second place five days? Without knowledge of the particulars of your situation, Intro. to C++ sounds to me more like punishment than incentive. And I like C++. One important instinct for your programming career is sensitivity to easier. I strongly suspect, though, that there are real values in basic programming that your CADD software has not yet taught you. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
It is a homework assignment from a book but not for a class. I'm trying to teach my self some basic programming before I have to take it in college. If I show enough understanding of the subject, my advisor will let me forgo Intro. to Programming and go into Intro. to C++. What civil engineers need with all this programming is beyond me. We have to learn another language to program our CADD software, which I find much easier than this. But needless to say, I'm stumped on this problem. I keep ending up in a never ending loop. Shanna Mike Meyer wrote: lostinpython [EMAIL PROTECTED] writes: I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n 2 is prim if no number between 2 and sqrt of n (inclusivly) evenly divides n. How about this (untested): import sys import subprocess primes = subprocess.Popen([primes, sys.argv[1], sys.argv[1]], stdout=subprocess.PIPE).stdout.readlines() if primes: print sys.argv[1], prime else: print sys.argv[1], not prime Seriously, this sounds like a homework assignment. Google for sieve of eratosthenes. The BSD primes program I used in the above is an implementation of that in C. If it isn't a homework assignment, and you're honestly in such, then you should know there's been a lot of research in this area, because primes are important in cryptographic applications. Once again, google is a good place to start on looking for recent research on the subject. mike -- Mike Meyer [EMAIL PROTECTED] http://www.mired.org/home/mwm/ Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
lostinpython said unto the world upon 2005-05-30 02:50: It is a homework assignment from a book but not for a class. I'm trying to teach my self some basic programming before I have to take it in college. If I show enough understanding of the subject, my advisor will let me forgo Intro. to Programming and go into Intro. to C++. What civil engineers need with all this programming is beyond me. We have to learn another language to program our CADD software, which I find much easier than this. But needless to say, I'm stumped on this problem. I keep ending up in a never ending loop. Shanna Hi Shanna, Since you are just beginning, I'd like to recommend the tutor list http://mail.python.org/mailman/listinfo/tutor. It is not that newcomers are not welcome here. But the folks who populate the tutor list are particularly good at answering neophytes' questions at the level. Since you've got some code together, even though it isn't doing what you want, you've already got a decent start for getting help. Post the question and the code to the tutor list and I'd not be surprised if you will soon be well on your way to solving your problem. Best, Brian vdB Who owes much of what he knows about Python to the tutor list. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
What civil engineers need with all this programming is beyond me. One of my best friends and expartner and top civil-structural engineers in the country (he built Dallas Reunion Arena and many other complex structures) was an ace programmer in many languages. He was not willing to just accept the results of canned packages, he wanted to know where the answers came from and make software that made sense to his engineers. I presume you are young and if you wish to be an engineer and not a salesman you must be eaten up with the desire to know How Stuff Works. Computers are ubiquitous in engineering and if you want to be the best, learn how they work. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
lostinpython wrote: But needless to say, I'm stumped on this problem. I keep ending up in a never ending loop. I've been told that the trick with recursion/iteration is to always determine what your ending condition is first, and then construct the body of the recursion/loop to reach that ending condition eventually. If you post the specific code which is giving you problems, people here can point out why you're missing the exit. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
lostinpython I'm having trouble writing a program that figures lostinpython out a prime number. Does anyone have an idea on how lostinpython to write it? [I can't quite tell from your posts what your level of programming knowledge is, so I've aimed low. If this was wrong, please accept my apologies. --rdh] It's not quite clear precisely what the problem is. Do you want to find all primes less than some number N, or find the prime factorization of some input number, or something else altogether? Are there any other constraints? Ie, does the program have to be recursive? I'm going to assume that you want to find all primes less than N, and that are no constraints on the form of the program. First, pretend you have a function called is_prime. It will look something like this: def is_prime(n): # return True if n is prime, False otherwise # magic goes here If we had this function, the our main program would look something like this: N = 20 for n in range(1, N+1): if is_prime(n): print n NOTE: range(1,N+1) returns a list of numbers from 1 to N inclusive. The question now is how to fill in the missing part of is_prime. In your original post, you noted that n2 is prime if no number between 2 and sqrt(n) inclusive divides into n evenly. This tells us that we have to test a list of possible factors for divisibility into n. Ignoring, for a little while, how we figure out the possible factors, we can now expand is_prime as follows: def is_prime(n): # return 1 if n is prime, 0 otherwise from math import sqrt for i in possible_factors: # if i divides n, n isn't prime # if no i divided into n, ie, we fell out of the loop, # n is prime The possible factor i divides into n if n % i == 0. Once we've decided that n is or isn't prime, we can just return True or False respectively. Adding these details: def is_prime(n): # return 1 if n is prime, 0 otherwise from math import sqrt for i in possible_factors: if n % i == 0: return True return False The final step is to figure out the list of possible factors. By the definition, this is the list of integers from 2 to the integer value of sqrt(n), inclusive. To get this list, we can use the range function again, assuming that sqrt(n) to compute the square root for us. The list of possible factors is given by range(2, int(sqrt(n)) + 1) The final trick to is to get the definition of sqrt. It turns out that this function is defined in the math module. Adding the bit of syntax needed to access the sqrt function, we have: def is_prime(n): # return 1 if n is prime, 0 otherwise from math import sqrt for i in range(2, int(sqrt(n)) + 1): if n % i == 0: return False return True Put together with the main program above, this will print out a list as follows: 1 2 3 5 7 11 13 17 19 However, there's a slight problem here. By definition, 1 is not a prime. We could fix this a couple of ways. Either we could change the main program not to start its range with 1, or we can fix is_prime. The latter is simple: def is_prime(n): # return 1 if n is prime, 0 otherwise from math import sqrt if n == 1: return False for i in range(2, int(sqrt(n)) + 1): if n % i == 0: return False return True Another algorithm mentioned in the followups to your posting is the Sieve of Eratosthenes, named for its ancient Greek discoverer. You can find a description of the Sieve in many places on the web. Trying to implement it might be a good next step. Dale. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
Sigh ... one of my intermediate versions of is_prime() returns True if the n is *not* prime, and false otherwise. The final version is correct, though. Dale. -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
On 29 May 2005 19:55:32 -0700, lostinpython [EMAIL PROTECTED] wrote: I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n 2 is prim if no number between 2 and sqrt of n (inclusivly) evenly divides n. This sounds remarkably like a homework problem, so I'm not going to give you a full answer. Perhaps if you could be more specific about which part's giving you trouble we could help you out with that. If it finding square roots? is it checking for divisibility? is it getting the loop to run through correctly? Is it some other problem? Tim -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: prime number
lostinpython [EMAIL PROTECTED] writes: I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n 2 is prim if no number between 2 and sqrt of n (inclusivly) evenly divides n. How about this (untested): import sys import subprocess primes = subprocess.Popen([primes, sys.argv[1], sys.argv[1]], stdout=subprocess.PIPE).stdout.readlines() if primes: print sys.argv[1], prime else: print sys.argv[1], not prime Seriously, this sounds like a homework assignment. Google for sieve of eratosthenes. The BSD primes program I used in the above is an implementation of that in C. If it isn't a homework assignment, and you're honestly in such, then you should know there's been a lot of research in this area, because primes are important in cryptographic applications. Once again, google is a good place to start on looking for recent research on the subject. mike -- Mike Meyer [EMAIL PROTECTED] http://www.mired.org/home/mwm/ Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information. -- http://mail.python.org/mailman/listinfo/python-list
