Re: A try on a is_prime function

[Peter Cawley <lua@...>]

* I'd declare "function add_primes()" as "local function add_primes()"
* "for x, _ in" can be written as just "for x in" if you're not using
the "_" variable
* "local primes = { [2] = true, [3] = true }" is less clear, but a
tiny bit more memory efficient as "local primes = {nil, true, true}"
* "floor( max_prime / x ) * x" is probably more efficient as
"max_prime - (max_prime % x)"
* "return primes[ n ] == true" may be more efficient as "return not
not primes[n]"
* "max_prime = table.maxn( t )" might be more efficient if rolled into
the preceeding for loop; "if x > max_prime then max_prime = x end"

On Mon, Apr 27, 2009 at 5:10 PM, Matthias Kluwe <mkluwe@gmail.com> wrote:
> Hi!
>
> For a presentation of lua for mathematicians I tried to come up with a
> is_prime function.
>
> This is what I got:
>
> local function is_prime()
>  local primes = { [2] = true, [3] = true }
>  local max_prime = 3
>  local floor = math.floor
>  function add_primes()
>    local t = {} -- list of candidates
>    local N = max_prime * 2 + 1
>    for i = max_prime + 2, N, 2 do
>      t[ i ] = true
>    end
>    -- sieve candidates
>    for x, _ in pairs( primes ) do
>      for i = floor( max_prime / x ) * x, N, x do
>        t[ i ] = nil
>      end
>    end
>    -- append primes
>    for x, _ in pairs( t ) do
>      primes[ x ] = true
>    end
>    max_prime = table.maxn( t )
>  end
>  return function( n )
>    while n > max_prime do
>      add_primes()
>    end
>    return primes[ n ] == true
>  end
> end
> is_prime = is_prime()
>
> Now, if you like to tiker around with such things for recreational
> purposes (like me), please comment. The result should be
>
> * easy to understand
> * concise
> * performant
>
> Regards,
> Matthias
>