Crivo de Eratóstenes em Lua

--O Crivo de Eratóstenes é um método simples de se achar
--os números primos em um intervalo de 1 a n.

--Ele consiste em montar uma tabela com os números que serão
--testados, e iterar do 2º ao n-ézimo elemento, invalidando
--todos os números da tabela que são divisíveis pelo contador
--da iteração (e que também são diferentes do contador).

--Abaixo segue uma implementação em linguagem Lua

-- Gera uma tabela contendo os números de 1 a n
function geraNumeros(n)
local arr = {}
for i = 1, n do
arr[i] = true
end
return arr
end

-- Deixa como true os índices primos
function filtraPrimos(arr)
local count = #arr
for c = 2, count do
if(arr[c]) then
for i = c + c, count, c do
arr[i] = false
end
end
end
return arr
end

local arr = geraNumeros(99999)

arr = filtraPrimos(arr)

-- Imprime os números primos de 1 a n
table.foreach(arr, function(i,v) if v then print(i) end end)

--FONTE: http://kknd.wordpress.com/