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