https://www.lua.org/cgi-bin/demo?sieve: Eratosthenes' sieve?

[Thorkil Naur <naur@...>]

Dear List,

The demonstration program https://www.lua.org/cgi-bin/demo?sieve is:

  -- 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

This is a wonderful program in many ways and I fully agree with its use
as a demonstration. However, the method used is simple trial division,
not the sieve of Eratosthenes. So I suggest that the comment is adjusted
acordingly, for example to say "prime filtering by trial division
programmed with coroutines" or similarly.

To support this view, instrument sieve.lua slightly:

  $ diff -u sieve.lua sieve2.lua
  --- sieve.lua   2021-04-14 19:59:22.000000000 +0200
  +++ sieve2.lua  2021-05-09 19:58:26.000000000 +0200
  @@ -16,6 +16,7 @@
   function filter (p, g)
     return coroutine.wrap(function ()
       for n in g do
  +      print( n .. "%" .. p .. " = " .. n%p )
         if n%p ~= 0 then coroutine.yield(n) end
       end
     end)
  $

Running the instrumented version shows what happens:

  $ lua-5.4.3 -e'N=15' sieve2.lua
  2
  3%2 = 1
  3
  4%2 = 0
  5%2 = 1
  5%3 = 2
  5
  6%2 = 0
  7%2 = 1
  7%3 = 1
  7%5 = 2
  7
  8%2 = 0
  9%2 = 1
  9%3 = 0
  10%2 = 0
  11%2 = 1
  11%3 = 2
  11%5 = 1
  11%7 = 4
  11
  12%2 = 0
  13%2 = 1
  13%3 = 1
  13%5 = 3
  13%7 = 6
  13%11 = 2
  13
  14%2 = 0
  15%2 = 1
  15%3 = 0
  $

So: Each candidate is divided by the primes less than the candidate. And
if all remainders are non-zero, the number is printed as prime.

This is in contrast to the sieve of Eratosthenes
(https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes): Initially, the
desired candidates are listed:

  2 3 4 5 6 7 8 9 10 11 12 13 14 15

Then numbers divisible by the first number in the list, 2, except 2
itself, are marked as composite (enclosed in ()s):

  2 3 (4) 5 (6) 7 (8) 9 (10) 11 (12) 13 (14) 15

Then numbers divisible by 3, the next unmarked number, are marked:

  2 3 (4) 5 (6) 7 (8) (9) (10) 11 ((12)) 13 (14) (15)

(Marking starts at 3*3 = 9, because 6 = 2*3 has already been marked
as divisible by 2.)

And then we are done, since the next number to be marked, 5*5 = 25, is
beyond the list. The primes less than 15 are the unmarked numbers left:

  2 3 5 7 11 13

Clearly, this process is quite different from what happens in sieve.lua.

The view that the sieve.lua program is not really an implementation of
Eratosthenes' sieve is inspired by a similar view, expressed by Melissa
E. O’Neill in "The Genuine Sieve of Eratosthenes"
(https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf), concerning the
following "much beloved and widely used example" Haskell program for
generating primes:

  primes = sieve [2..]
  sieve (p : xs) = p : sieve [x | x <− xs, x ‘mod‘ p > 0]

I will spare the reader a discussion of this Haskell program, except for
noting that the code is actually prominently displayed on the
haskell.org web site (2021-May-09), with "sieve" renamed to
"filterPrime". Reading O'Neill's paper may provide further support to
the view that sieve.lua is not an implementation of Eratosthenes' sieve.

Best regards
Thorkil Naur