“for”和/或“if, then”语句出现问题。

2011-7-25 5:38:45
收藏：0
阅读：107
评论：2

这是一个生成质数的看似简单的函数，但它并不像预期的那样工作。我已经搜索了在线指南，但似乎无法理解它。非常感谢您的帮助。

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”循环的方法是什么？

谢谢，Vince

编辑：像建议的那样将传递的参数限制为其平方根。

原文链接 https://stackoverflow.com/questions/6811931

点赞
stackoverflow用户830149
stackoverflow用户830149

我认为你只需要颠倒 for 循环的顺序。目前你是对每个数字都进行3、4、5等的测试，然后再对每个数字进行四次测试，然后再对每个数字进行五次测试等等。如果你交换两个“for”语句，你将首先比较 3、4、5...与第一个数字，然后比较 3、4、5...与第二个数字，然后比较 3、4、5...与第三个数字等等。

编辑

事实上，您需要做更多的工作。你必须确保 3、4、5...都不会被这个数字整除，然后在内部 for 循环之后，如果没有其他结果，就插入这个数字。此外，你应该限制内部循环到 sqrt(v) 停止，因为如果没有 sqrt(v) 下的任何数整除 v，那么除了 v 之外，也没有 sqrt(v) 以上的数。

编辑

事实上，我认为我误解了你的代码，你应该忽略我说的话。将内部循环限制为 sqrt(v)，但是除此之外，遵循 BMitch 的建议。

2011-07-25 05:03:47
stackoverflow用户596285
stackoverflow用户596285

你插入的太快了，在插入之前必须完成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 -- 如果可以整除，则不是质数
            is_prime=false
            break
        end
        if v > i_rt then -- 为了提高效率，一旦超过i的平方根，就退出
          break
        end
     end
     if is_prime then
         table.insert(t, i) -- 如果是质数，则插入
     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
2011-07-25 12:32:46

作者:

stackoverflow用户718242

stackoverflow用户718242
推荐文章