找質數

function prime(max_value)

    local value = 5;

    local index = 2;

    local root_index = 2;

    local limit = value * value;

    local p = {};

--  local count = 0;

--  initial first value start at 5

    p[1]=2;

    p[2]=3;

--  start find prime

    while value <= max_value do

        local sub_index=2;

        local check_not_prime = 0;

        while sub_index <= root_index do

--          count = count + 1; print(count,value,limit,index,sub_index,p[sub_index]);

        if (value % p[sub_index]) == 0 then check_not_prime = 1; break; end

            sub_index = sub_index + 1;

        end

        if check_not_prime == 0 then

          index = index + 1;

          p[index] = value;

        end

        value = value + 2;

        if( value >= limit ) then

            root_index = root_index + 1;

            limit = p[root_index+1] * p[root_index+1];

        end

    end

-- print all prime

    for i,j in pairs(p) do

        print(i,j);

    end

end

 

-- test

prime(100);

 

-- 程式結束

 

結果使用矩陣p{}儲存，所以要知道目前已有多少數目以index記錄。

已知只要找到現在驗證值value的開根以下的質數做驗證，所以加入root_index告知。

而現值超過上次有效質數平方limit，則要再更新。