-1

我一直在研究 ruby​​ 并且一直在做一些 ruby​​ 练习来看看我知道多少（这不是很多）。这是我遇到的一个问题：

问：编写一个方法 is_prime?，它接受一个数字 num，如果它是素数则返回 true，否则返回 false。

您可能希望使用模运算： 5 % 2 在将 5 除以 2 时返回余数： 1. 如果 num 可被 i 整除，则 num % i == 0。（您不会期望已经知道模挑战）

这个问题也有一个答案，那就是。

A：

# Works for values greater than 1

def is_prime?(num)
  i = 2
  while i < num
    is_divisible = ((num % i) == 0)

    if is_divisible
      # divisor found; stop and return false!
      return false
    end

    i += 1
  end

  # no divisors found
  true
end

这就是我想出的：

嘛：

def is_prime?(num)
  if num % 2 == 0
    puts "false"
  else 
    puts "true"
  end
end

由于我所拥有的与答案完全不同，因此我可以使用支持我的人来查看我是否走在正确的轨道上。谢谢你。

4

4 回答 4

2

开始编写自动化测试。具体来说...

assert{ 5.is_prime }
deny{ 6.is_prime }
assert{ 7.is_prime }
deny{ 8.is_prime }
deny{ 9.is_prime }

如果您is_prime使用return true而不是print "true"，我的最后一个断言会破坏它。（我在这里使用了错误的库，但你可以使用assert_true()你的库附带的任何断言test/unit。）

继续添加断言，并在代码中断时修复代码，直到您的代码看起来像该代码。然后查找“埃拉托色尼筛法”的标准实现，了解为什么该代码效率低下！

于 2013-11-03T23:21:20.097 回答
2

您的解决方案仅检查数字是否为偶数，并且正如 Cary Swoveland 指出的那样，会错误地将 2 识别为非素数。您还会错误地将 9 或 15 等数字识别为素数。

您可以做几件事来大大加快提供的解决方案：

  1. 在检查num不能被 2 整除后，您只需要检查超过该点的奇数。将候选除数增加 2 而不是 1。
  2. 在循环的上限，while您需要检查的最大候选除数是Math.sqrt(num)。任何num大于平方根的因子都有一个小于平方根的辅助因子，因此查看较大的候选者没有意义。
于 2013-11-03T23:32:24.740 回答
1

您的解决方案仅适用于确定一个数字是否可以被 2 整除。

例如，输入值 9 将导致您的函数返回 true，即使 9 不是素数。它需要迭代所有可能的因素，而不仅仅是 2，就像它在示例解决方案中所做的那样。

于 2013-11-03T23:18:24.607 回答
0

要通过尝试除法来做到这一点，这似乎是您想要做的，最简单的方法是从 i = 2 开始并执行 i % num == 0。然后在 i 小于 num 时将 i 连续增加 1 .

此外，要使这适用于负数，请检查是否 num <= 1。如果是，则返回 false。

优化1：（容易）不要一直到数字。只能达到数字的平方根。要轻松完成此操作，请设置循环条件 (i*i <= num)

优化 2：（具有挑战性）从 3 开始，然后增加 2，因为任何可被 2 整除的数字都不能是素数。当然除了2。

为了使这项工作，您需要在代码的开头添加另外两个检查（阅读：if 语句）。第一个检查是否（num == 2）。如果是，则返回 true。第二个检查是否（num % 2 == 0）。如果是，则返回 false；

优化3：（困难）你只需要检查素数。如果您生成并存储素数列表，则可以使用这些素数快速找到远大于列表中最高素数的素数。一旦你理解了优化 2，你就可以很容易地写出来。

一旦你掌握了试验部门，你可能想看看埃拉托色尼筛。这是很酷的豆子，也不难理解。

于 2013-11-07T17:10:47.147 回答