-- sieve of eratosthenes

function primes (n)

    max_index = math.floor((n-1)/2)

    v = {}
    for i = 1, max_index do
        v[i] = true
    end

    p = 3
    while p*p <= n do
        i = math.floor(p/2)
        if v[i] then
            for j = 2*i*(i+1), max_index, p do
                v[j] = false
            end
        end
        p = p + 2
    end

    ps = {2}
    for i = 1, max_index do
        if v[i] then
            table.insert(ps, 2*i+1)
        end
    end

    return ps

end

print(#(primes(1000)))