Sweet Snippet 系列之 埃拉托斯特尼(Eratosthenes)筛法

function Eratosthenes(n)
    local is_prime = {}
    
    -- init is_prime map
    for i = 2, n do
        is_prime[i] = true
    end
    
    -- eratosthenes filter
    local beg_val = 2
    local end_val = math.floor(math.sqrt(n))
    
    for i = beg_val, end_val do
        if is_prime[i] then
            for j = i + i, n, i do
                is_prime[j] = false
            end
        end
    end
    
    -- get primes
    local primes = {}
    for i = 2, n do
        if is_prime[i] then
            table.insert(primes, i)
        end
    end
    
    return primes
end

print(#Eratosthenes(100)) // output 25