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