deps/lua/test/sieve.lua

   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