Sieve of Eratosthenes performance question

["Shoaib Meenai" <shobiz91@...>]

To get the hang of programming in Lua, I wanted to write a program
which computed all the prime numbers up to a limit using the Sieve of
Eratosthenes, and then stored all the primes in a table. I came up
with two ways to do so (both programs are for Lua 5.1.2):


Program 1:

local n = ... or 1000
local prime = {}
local primes = {}

for i = 2, n do prime[i] = true end

for i = 2, n do
 if prime[i] then
   primes[#primes+1] = i
   for j = i*2, n, i do prime[j] = false end
 end
end

-- print(table.concat(primes, " "))


Program 2:

local n = ... or 1000
local composite = {}
local primes = {}

for i = 2, n do
 if not composite[i] then
   primes[#primes+1] = i
   for j = i*2, n, i do composite[j] = true end
 end
end

-- print(table.concat(primes, " "))


(The last lines are commented out because I wanted to measure the time
taken to perform the calculations)


Both programs are in effect the same, and I expected both to have a
similar performance. However, on my machine, the first program takes 7
seconds for n = 5000000, but the second takes 12 seconds! What's the
reason for the performance discrepancy?