| -- The Great Computer Language Shootout | |
| -- http://shootout.alioth.debian.org/ | |
| -- contributed by Mike Pall | |
| local floor, ceil = math.floor, math.ceil | |
| local precision = 50 -- Maximum precision of lua_Number (minus safety margin). | |
| local onebits = (2^precision)-1 | |
| local function nsieve(p, m) | |
| local cm = ceil(m/precision) | |
| do local onebits = onebits; for i=0,cm do p[i] = onebits end end | |
| local count, idx, bit = 0, 2, 2 | |
| for i=2,m do | |
| local r = p[idx] / bit | |
| if r - floor(r) >= 0.5 then -- Bit set? | |
| local kidx, kbit = idx, bit | |
| for k=i+i,m,i do | |
| kidx = kidx + i | |
| while kidx >= cm do kidx = kidx - cm; kbit = kbit + kbit end | |
| local x = p[kidx] | |
| local r = x / kbit | |
| if r - floor(r) >= 0.5 then p[kidx] = x - kbit*0.5 end -- Clear bit. | |
| end | |
| count = count + 1 | |
| end | |
| idx = idx + 1 | |
| if idx >= cm then idx = 0; bit = bit + bit end | |
| end | |
| return count | |
| end | |
| local N = tonumber(arg and arg[1]) or 1 | |
| if N < 2 then N = 2 end | |
| local primes = {} | |
| for i=0,2 do | |
| local m = (2^(N-i))*10000 | |
| io.write(string.format("Primes up to %8d %8d\n", m, nsieve(primes, m))) | |
| end |