summaryrefslogtreecommitdiffstats
path: root/deps/lua/test/sieve.lua
diff options
context:
space:
mode:
Diffstat (limited to 'deps/lua/test/sieve.lua')
-rw-r--r--deps/lua/test/sieve.lua29
1 files changed, 29 insertions, 0 deletions
diff --git a/deps/lua/test/sieve.lua b/deps/lua/test/sieve.lua
new file mode 100644
index 0000000..0871bb2
--- /dev/null
+++ b/deps/lua/test/sieve.lua
@@ -0,0 +1,29 @@
+-- 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 math.mod(n, p) ~= 0 then coroutine.yield(n) end
+ end
+ end)
+end
+
+N=N or 1000 -- 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