1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
local bench = script and require(script.Parent.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")