• Subject: Sieve of Eratosthenes performance question
• From: "Shoaib Meenai" <shobiz91@...>
• Date: Wed, 6 Jun 2007 12:37:32 +0500

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

```