Remarkable results with psyco and sieve of Eratosthenes

[dickinsm at gmail.com]

On Nov 29, 6:59 pm, "Steve Bergman" <s... at rueb.com> wrote:
> dicki... at gmail.com 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