From: Dee Zsombor <Dee.Zsombor@...>
Date: 2005-06-22T17:20:36+09:00
Subject: Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

How about using a better algorithm than  Eratosthenes sieve invented
thousands of years ago. In late 2003 a new method was published that
computes the first n primes using binary quadratic forms. This will
give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).

For theoretical description see:
http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf

And for a sample implementation in C
http://cr.yp.to/primegen.html

cheers,
zsombor
--
http://deezsombor.blogspot.com