[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**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?