Problem with "for" and/or "if, then" statement(s)

Here is a seemingly simple function to generate prime numbers. However, it does not work as expected. I have trawled the online guides but I can't seem to get my head around i开发者_如何学Pythont. Your help is much appreciated.

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

When I do:

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

I get:

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

9 and 15 are not prime numbers, and it looks like the second "for" loop is not going past the first element in the table(2). What is the correct way to use the "for" loop in this case?

Thanks, Vince

EDIT: limited the passed in argument to its square root as suggested.

You're inserting too soon, you have to finish the for loop before you do the insert. Here's one way:

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

And an example:

> 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

I think you just need to flip the order of your for loops. As it is, you're testing 3 against every number, then four against every number, then five against every number, and so on. If you switch your two "for" statements, you'll compare 3,4,5... against the first number, 3,4,5... against the second number, 3,4,5... against the third number and so on.

EDIT

Actually, you'll have to do a bit more. You have to make sure that none of 3,4,5... divide the number, and then after the inner for loop, insert the number if nothing has gone in. Furthermore, you should limit your inner loop to stop at sqrt(v), because if nothing under the sqrt(v) divides v, then nothing over sqrt(v) will either (besides v).

EDIT

Actually, I think I misinterpreted your code, and you should ignore what I said. Limit the inner loop to sqrt, but other than that, go with what BMitch said.