I think this misrepresents lua. Lua has many fine features (tables, dynamic typing, local functions, and so on). However, the crucial selling point is embedding and extending. Something like LGMP's probab_prime (implemented by wrapping the GNU Multiple Precision library) would be more essentially lua-ish, and more performant as well.

Johnicholas

LGMP is here:

http://members.chello.nl/~w.couwenberg/lgmp.htmGMP is here:

http://gmplib.org/-----Original Message-----

From:

[hidden email] on behalf of Matthias Kluwe

Sent: Mon 4/27/2009 12:53 PM

To: Lua list

Subject: Re: A try on a is_prime function

Hi!

Thanks for the quick reaction.

2009/4/27 Peter Cawley <

[hidden email]>:

> * I'd declare "function add_primes()" as "local function add_primes()"

Yes, that has been a typo.

> * "for x, _ in" can be written as just "for x in" if you're not using

> the "_" variable

Of course. You can see my low lua experience here...

> * "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]"

I hope so.

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

Ok, as table.maxn iterates over the table itself, that should be a good idea.

Including your suggestions, here's the revised version:

local function is_prime()

local primes = { [2] = true, [3] = true }

local max_prime = 3

local floor = math.floor

local 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

if x > max_prime then max_prime = x end

end

end

return function( n )

while n > max_prime do

add_primes()

end

return primes[ n ] == true

end

end

is_prime = is_prime()

Regards,

Matthias