sieve.lua

local function prequire(name) local success, result = pcall(require, name); return success and result end
local bench = script and require(script.Parent.bench_support) or prequire("bench_support") or require("../bench_support")

function test()

  -- the sieve of of Eratosthenes programmed with coroutines
  -- typical usage: lua -e N=1000 sieve.lua | column

  -- generate all the numbers from 2 to n
  function gen (n)
    return coroutine.wrap(function ()
      for i=2,n do coroutine.yield(i) end
    end)
  end

  -- filter the numbers generated by `g', removing multiples of `p'
  function filter (p, g)
    return coroutine.wrap(function ()
      while 1 do
        local n = g()
        if n == nil then return end
        if n % p ~= 0 then coroutine.yield(n) end
      end
    end)
  end

  local ts0 = os.clock()

  for loops=1,100 do
    N = 1000
    x = gen(N)		-- generate primes up to N
    while 1 do
      local n = x()		-- pick a number until done
      if n == nil then break end
      -- print(n)		-- must be a prime number
      x = filter(n, x)	-- now remove its multiples
    end
  end

  local ts1 = os.clock()

  return ts1-ts0
end

bench.runCode(test, "sieve")