lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

I consider myself thoroughly beaten. Not that this was a competition or anything but wow.

On 6 April 2010 03:24, Mike Pall <> wrote:
Linus Sjögren wrote:
> Nice! I noticed a speed improvement in my prime finder:
> beta2:
> >189.43 seconds spent - 15485863 is the 1000000th prime.
> beta4:
> >143.27 seconds spent - 15485863 is the 1000000th prime.

Ah, interesting. But whatever algorithm you use is a tad slow.
Even the naive Sieve of Eratosthenes finds all primes in less
than a second (and there are other, much better algorithms).

See the attached program for a variant using bit operations. It
counts the primes up to a maximum, not the other way round. Run it
with 15485863 as the argument to get a comparable timing.