Lua - 计算从1到n的质数

2014-10-3 0:47:6
收藏：0
阅读：69
评论：1

我非常新手Lua编程语言，只是通过我机器人团队的导师学习它。他们向我们挑战一个问题，即打印出444以内的所有质数。我的尝试是：

isPrime = true

for i = 2, math.floor(math.sqrt(444)) do
     for n = 2, i-1 do
           if i % n == 0 then
                isPrime = false
           end
      end
if isPrime == true then
      print(i)
end
end

然而，程序只输出了2和3。我的问题在哪里？

点赞
用户365496
用户365496

循环如果isPrime为真，则打印出一个数字，但是当检查值4时，isPrime被设置为false，而且没有任何东西可以再次将其设置为真。

您的程序由外部循环和内部循环组成，用于检查每个要检查的数字。

内部循环设计为对于质数它不会触及isPrime，对于复合数它会将isPrime设置为false。因此，对于质数，isPrime的值将是内部循环开始之前设置的任何值。由于您希望isPrime在质数结束时为true，因此您应该在内部循环之前将isPrime设置为true。

一旦您这样做，您的程序仍然存在漏洞。您的算法有点混淆了sqrt(n)的确切位置。

一些其他建议：

习惯使用局部变量而不是全局变量。这将有助于避免意外重置您不打算重置的变量引发错误的情况。

local isPrime = true

使用一致的缩进。这将有助于任何人阅读您的代码。在这种情况下，您的if isPrime == true then print(i) end代码没有缩进足够。

您可以在if条件中跳过== true：if isPrime then print(i) end。

有一种更好的算法可以查找到某个值下的所有质数，称为 埃拉托斯特尼筛选法。以下是在Lua中实现的代码：

function sieve_of_eratosthenes(n)
  local is_prime = {}

  for i = 1, n do
    is_prime[i] = 1 ~= i
  end

  for i = 2, math.floor(math.sqrt(n)) do
    if is_prime[i] then
      for j = i*i, n, i do
        is_prime[j] = false
      end
    end
  end

  return is_prime
end

local primes = sieve_of_eratosthenes(444)

for key, value in pairs(primes) do
  if (value) then
    print(key)
  end
end
2014-10-03 00:52:57

作者:

用户4104337

用户4104337
推荐文章