  lua-l archive

• Subject: Re: [ANN] LuaJIT-2.0.0-beta4
• From: Mike Pall <mikelu-1004@...>
• Date: Tue, 6 Apr 2010 03:24:07 +0200

```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.

--Mike
```
```-- This is the (naive) Sieve of Eratosthenes. Public domain.

local bit = require("bit")
local band, bxor, rshift, rol = bit.band, bit.bxor, bit.rshift, bit.rol

local function nsieve(m)
local p, count = {}, 0
for i=0,rshift(m, 5) do p[i] = -1 end
for i=2,m do
if band(rshift(p[rshift(i, 5)], i), 1) ~= 0 then
count = count + 1
for j=i+i,m,i do
local jx = rshift(j, 5)
p[jx] = band(p[jx], rol(-2, j))
end
end
end
return count
end

local N = tonumber(arg and arg) or 1000
io.write(string.format("Primes up to %d: %d\n", N, nsieve(N)))
```