Проблема с утверждением (ями) for и / или if

Question

Вот, казалось бы, простая функция для генерации простых чисел. Тем не менее, это не работает, как ожидалось. Я просмотрел онлайн-справочники, но, похоже, не могу понять, как это сделать. Ваша помощь очень ценится.

primes = function(limit)
local t = {2}
for i = 3, math.sqrt(limit) do
    for k, v in ipairs(t) do
        if i % v == 0 then -- check if "i" is evenly divisible by each table element
            break
        else table.insert(t, i) -- if it is not, it is a prime number
            break
        end
     end
 end
 return t
 end

Когда я делаю:

 for k, v in ipairs(primes(15)) do print (k, v) end

Я получаю:

1   2
2   3
3   5
4   7
5   9
6   11
7   13
8   15

9 и 15 не являются простыми числами, и похоже, что второй цикл «for» не проходит мимо первого элемента в таблице (2). Как правильно использовать цикл for в этом случае?

Спасибо, Винс

РЕДАКТИРОВАТЬ: ограничил передаваемый аргумент своим квадратным корнем, как было предложено.

Answer 1

Вы вставляете слишком рано, вы должны закончить цикл for, прежде чем делать вставку. Вот один из способов:

primes = function(limit)
local t = {2}
local is_prime, i_rt
for i = 3, limit do
    is_prime=true
    i_rt=math.sqrt(i)
    for k, v in ipairs(t) do
        if i % v == 0 then -- evenly divisible, not prime
            is_prime=false
            break
        end
        if v > i_rt then -- break once you exceed square root of i for efficiency
          break
        end
     end
     if is_prime then
         table.insert(t, i) -- insert if it is a prime
     end
 end
 return t
 end

И пример:

> for k, v in ipairs(primes(50)) do print (k, v) end
1   2
2   3
3   5
4   7
5   11
6   13
7   17
8   19
9   23
10  29
11  31
12  37
13  41
14  43
15  47

Answer 2

Я думаю, вам просто нужно изменить порядок ваших циклов for. На самом деле вы тестируете 3 против каждого числа, затем четыре против каждого числа, затем пять против каждого числа и так далее. Если вы переключите два оператора «for», вы сравните 3,4,5 ... с первым числом, 3,4,5 ... со вторым числом, 3,4,5 ... с третий номер и т. д.

EDIT

На самом деле, вам придется сделать немного больше. Вы должны убедиться, что ни одно из 3,4,5 ... не делит число, а затем после внутреннего цикла for вставьте число, если ничего не произошло. Кроме того, вы должны ограничить свой внутренний цикл остановкой на sqrt v), потому что если ничто в sqrt (v) не делит v, то ничего кроме sqrt (v) тоже не будет (кроме v).

EDIT

На самом деле, я думаю, что я неправильно истолковал ваш код, и вы должны игнорировать то, что я сказал. Ограничьте внутренний цикл sqrt, но, кроме этого, следуйте словам BMitch.