4

这是我的 Lua 代码，用于接受用户输入，并检查输入的数字是否为素数。我的问题是程序认为任何偶数都不是素数，而任何奇数都是。

 print("Enter a number.")
 local number = io.read("*n")

 function prime(n)
 for i = 2, n^(1/2) do
   if (n % i) == 0 then
     return false
   end
   return true
 end
 end

 if prime(number) == true then
   print("Your number is prime!")
 end

 if prime(number) == false then
   print("Your number is not prime!")
 end
4

5 回答 5

9

移出return true循环。

因此：

function prime(n)
    for i = 2, n^(1/2) do
        if (n % i) == 0 then
            return false
        end
    end
    return true
end
于 2012-07-20T01:57:51.840 回答
5

我知道这是一个旧帖子，但由于它在谷歌的顶部附近，我认为发布我的主要查找器不会有什么坏处。它基本上对明显的东西进行了一些简单的检查，然后以与 Jon Ericson 帖子中的第一个示例类似的方式循环遍历剩下的内容。尚未对其进行基准测试，但它似乎可以很好地应对。

--returns true if prime
function isPrime(n)
    local n = tonumber(n)
    --catch nil, 0, 1, negative and non int numbers
    if not n or n<2 or (n % 1 ~=0) then 
        return false
    --catch even number above 2
    elseif n>2 and (n % 2 == 0) then 
        return false
    --primes over 5 end in 1,3,7 or 9
    --catch numbers that end in 5 or 0 (multiples of 5)
    elseif n>5 and (n % 5 ==0) then 
        return false
    --now check for prime
    else
        --only do the odds
        for i = 3, math.sqrt(n), 2 do
            --did it divide evenly
            if (n % i == 0) then
                return false
            end
        end
        --can defeat optimus
        return true
    end
end
于 2013-07-29T15:25:30.110 回答
5

你过早地返回真。只要任何 i满足条件，您就会返回 true。您必须将 return放在循环之后。

于 2012-07-20T01:56:37.970 回答
3

如果你要检查素数，你不妨选择一个有效的算法。正如一个答案（隐晦地）指出的那样，所有大于 2 的偶数都不是素数。因此，您可以对一半的数字进行短路检查，从而使检查任何特定数字的速度加倍：

function check_prime (x) 

  -- Negative numbers, 0 and 1 are not prime.
  if x < 2 then 
     return false
  end

  -- Primality for even numbers is easy.
  if x == 2 then
     return 2
  end
  if x%2 == 0 then
     return false
  end

  -- Since we have already considered the even numbers,
  -- see if the odd numbers are factors.
  for i = 3, math.sqrt(x), 2 do 
      if x%i == 0 then 
         return false
      end 
  end 
  return x 
end

我们可以应用各种优化，但让我们尝试以更 Lua 的方式来做这件事：

function sieve (x)
  if x < 2 then 
     return false
  end

  -- Assume all numbers are prime until proven not-prime.
  local prime = {}
  prime[1] = false
  for i = 2, x do 
      prime[i] = true 
  end 

  -- For each prime we find, mark all multiples as not-prime.
  for i = 2, math.sqrt(x) do
      if prime[i] then
         for j = i*i, x, i do
             prime[j] = false
         end
      end
  end

  return prime
end

要使用筛分功能：

prime = sieve(number)
if prime[number] then
   print("Your number is prime!")
else
   print("Your number is not prime!")
end

在我的测试中，sieve 版本的生成所有小于 100 万的素数的算法比之前的算法快 6 倍。（您的里程可能会有所不同。）您可以轻松地检查所有数字的素数，而number无需额外费用。另一方面，它使用更多的内存，如果你真的想只检查一个数字的素数，它的效率就会降低。

于 2013-03-03T07:16:51.153 回答
-3

我会通过将数字除以 2 并检查除法的下限是否等于除法来检查素数。它看起来像这样。

if (input/2 == math.floor(input/2)) then
  print("is prime")
else
  print("is not prime")
end
于 2012-09-13T23:37:50.960 回答