There's my attempt (luo.lua):
--
local floor = math.floor
local sqrt = math.sqrt
function primesieve(N)
local result = {2, 3}
if N < 2 then return {} end
if N < 3 then return {2} end
if N < 4 then return {2, 3} end
local c, k, t, q, M, S
c = 0
k = 1
t = 2
q = floor(sqrt(N)/3)
M = N // 3
S = {}
local step = 2
local first = 5
while first <= N do
S[#S+1] = first
first = first + step
step = step == 2 and 4 or 2
end
for i = 1, q, 1 do
k = 3 - k
c = c + 4*k*i
j = c
local ij = 2*i*(3-k)+1
t = t + 4*k
while j <= M do
S[j] = 0
j = j + ij
ij = t - ij
end
end
for _, v in next, S do
if v > 0 then
result[#result + 1] = v
end
end
return result
end
--Just for testing
for i = 1, 100 do
X = #primesieve(1000000)
end
--
My script takes 15~16 seconds to run, so I want to know if there's a better/faster way (or a better sieve) to code. I'm working with pure Lua solutions and I'm rather new to Lua and programming, so optimizing and co. are still alien to me. Sorry for the noobish question and thank you in advance.
Regards,
Jairo :)
