Subversion Repositories WoWGM

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
3 tristanc 1 
-- the sieve of of Eratosthenes programmed with coroutines
2 
-- typical usage: lua -e N=1000 sieve.lua | column
3 
 
4 
-- generate all the numbers from 2 to n
5 
function gen (n)
6 
  return coroutine.wrap(function ()
7 
    for i=2,n do coroutine.yield(i) end
8 
  end)
9 
end
10 
 
11 
-- filter the numbers generated by `g', removing multiples of `p'
12 
function filter (p, g)
13 
  return coroutine.wrap(function ()
14 
    while 1 do
15 
      local n = g()
16 
      if n == nil then return end
17 
      if math.mod(n, p) ~= 0 then coroutine.yield(n) end
18 
    end
19 
  end)
20 
end
21 
 
22 
N=N or 1000		-- from command line
23 
x = gen(N)		-- generate primes up to N
24 
while 1 do
25 
  local n = x()		-- pick a number until done
26 
  if n == nil then break end
27 
  print(n)		-- must be a prime number
28 
  x = filter(n, x)	-- now remove its multiples
29 
end