tests/Smoke/sieve.lua


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

-- sieve.lua
-- the sieve of Eratosthenes programmed with coroutines
-- typical usage: lua -e N=500 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 ()
    for n in g do
      if n%p ~= 0 then coroutine.yield(n) end
    end
  end)
end

N=N or 500      -- from command line
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