On Nov 29, 6:59 pm, "Steve Bergman" <[EMAIL PROTECTED]> wrote: > [EMAIL PROTECTED] wrote: > > > BTW, can this code be made any more efficient? > > > I'm not sure, but the following code takes around 6 seconds on my > > 1.2Ghz iBook. How does it run on your machine? > > Hmm. Come to think of it, my algorithm isn't the sieve.
Right. I guess the point of the sieve is that you don't have to spend any time finding that a given odd integer is not divisible by a given prime; all the multiplies are done up front, so you save all the operations corresponding to the case when x % y != 0 in your code. Or something. > Anyway, this is indeed fast as long as you have enough memory to handle > it for the range supplied. The sieve can be segmented, so that the intermediate space requirement for computing the primes up to n is O(sqrt(n)). (Of course you'll still need O(n/log n) space to store the eventual list of primes.) Then there are all sorts of bells and whistles (not to mention wheels) that you can add to improve the running time, most of which would considerably complicate the code. The book by Crandall and Pomerance (Primes: A Computational Perspective) goes into plenty of detail on all of this. Mark Dickinson -- http://mail.python.org/mailman/listinfo/python-list
