9

I am trying to create a program that will test whether a value is prime, but I don't know how. This is my code:

class DetermineIfPrime
def initialize (nth_value)
@nth_value = nth_value
primetest
end

def primetest
  if Prime.prime?(@nth_value)
   puts ("#{@nth_value} is prime")
  else
   puts ("This is not a prime number.")
  end
rescue Exception
puts ("#{$!.class}")
puts ("#{$!}")
 end
end

And every time I run that it returns this.

NameError
uninitialized constant DetermineIfPrime::Prime

I tried other ways to do the job, but I think this is the closest I can get.

I also tried this:

class DetermineIfPrime
def initialize (nth_value)
@nth_value = nth_value
primetest
end

 def primetest
 for test_value in [2, 3, 5, 7, 9, 11, 13] do
  if (@nth_value % test_value) == 0
   puts ("#{@nth_value} is not divisible by #{test_value}")
  else
   puts ("This is not a prime number since this is divisible by #{test_value}")
  break
  end
 end
 end
end

Or am I just doing something wrong?

4

10 回答 10

27

Ruby 内置了检查数字是否为素数的方法。

require 'prime'

Prime.prime?(2)  #=> true
Prime.prime?(4)  #=> false
于 2015-08-06T03:02:06.717 回答
14 
def is_prime?(num)
  return false if num <= 1
  Math.sqrt(num).to_i.downto(2).each {|i| return false if num % i == 0}
  true
end

首先，我们检查 0 和 1，因为它们不是素数。然后我们基本上只是检查每个小于num的数字，看看它是否相除。然而，正如这里所解释的，对于每个大于 的平方根的因子num，都有一个小于 的因子，因此我们只查看 2 和平方根之间的值。

更新

def is_prime?(num) return if num <= 1 (2..Math.sqrt(num)).none? { |i| (num % i).zero? } end

于 2015-05-12T16:05:40.440 回答
8

您收到的错误是因为您Prime的代码中不需要，您需要require Prime在文件中执行。

我在这里找到了一种很酷的方法来检查一个数字是否是素数：

class Fixnum
  def prime?
    ('1' * self) !~ /^1?$|^(11+?)\1+$/
  end
end

10.prime?
于 2014-05-01T07:03:00.433 回答
3

从算法的角度来看，检查一个数字是否为素数可以通过检查所有数字来完成，包括（向下舍入到前一个整数）所述数字的平方根。

例如，检查 100 是否为素数涉及检查直到 10 的所有内容。检查 99 意味着只检查 9。

**另一种思考方式**
每个因子都有一对（3是36的因子，3的对是12）。
该对位于平方根的另一侧（6 的平方根是 36, 3 < 6, 12 > 6）。
因此，通过检查一切直到平方根（并且不超过）确保您检查所有可能的因素。

正如您所做的那样，您可以通过列出要比较的素数来加快速度。如果您有一个相当小的最大限制，您可以只拥有一个素数列表并直接查找该数字是否为素数。

于 2012-08-01T15:45:00.877 回答
3 
def is_prime?(num)
   Math.sqrt(num).floor.downto(2).each {|i| return false if num % i == 0}
   true
end

大声笑很抱歉复活了一个超级老问题，但这是谷歌出现的第一个问题。

基本上，它遍历可能的除数，使用平方根作为最大数来检查以节省非常大的数字的时间。

于 2013-10-31T19:24:55.650 回答
2

为了回答您的问题，虽然您可以使用 Ruby 的 Prime 来解决问题，但我将编写代码自行回答。

考虑到您需要做的就是确定一个小于整数平方根的因子。任何大于整数平方根的数字作为一个因子都需要第二个因子才能将该数字呈现为乘积。（例如，15 的平方根大约是 3.8，所以如果你发现 5 作为一个因子，它只是因子对 3 和 5 的一个因子！！）

    def isPrime?(num)
        (2..Math.sqrt(num)).each { |i| return false if num % i == 0}
        true
    end

希望有帮助！！

于 2013-11-20T03:30:01.187 回答
1

尝试这个

def prime?(num)
    2.upto(Math.sqrt(num).ceil) do |i|
        break if num%i==0
        return true if i==Math.sqrt(num).ceil   
    end
    return false
end
于 2014-05-25T15:40:56.490 回答
1

如果您要使用任何 Prime 函数，则必须包含 Prime 库。然而，这个问题可以在不使用主库的情况下解决。

def isPrime?(num)
  (2..Math.sqrt(num)).each { |i|
  if num % i == 0 && i < num
    return false
  end
  }
  true
  end

像这样的东西会起作用。

于 2012-10-14T12:41:25.587 回答
1

（首先回答这个问题：是的，你做错了什么。正如 BLUEPIXY 所提到的，你需要在require 'prime'调用的行上方放置某个地方Prime.prime?。通常在第 1 行。）

现在，已经给出了很多不使用的答案Prime.prime?，我认为对其中一些进行基准测试可能会很有趣，以及我自己的想法可能会有所改进。

TL;博士

我对几个解决方案进行了基准测试，包括我自己的几个；使用while循环并跳过偶数表现最好。

测试方法

以下是我从答案中使用的方法：

require 'prime'

def prime1?(num)
  return if num <= 1
  (2..Math.sqrt(num)).none? { |i| (num % i).zero? }
end

def prime2?(num)
  return false if num <= 1
  Math.sqrt(num).to_i.downto(2) {|i| return false if num % i == 0}
  true
end

def prime3?(num)
  Prime.prime?(num)
end

def prime4?(num)
  ('1' * num) !~ /^1?$|^(11+?)\1+$/
end

prime1?是 AndreiMotinga 的更新版本。是他的原始版本（删除prime2?了多余的方法）。是重新启动的，使用库。是 Saurabh 的正则表达式版本（减去猴子补丁）。eachprime3?primeprime4?Fixnum

更多测试方法

我想到的改进是利用偶数不能是素数的事实，并将它们排除在迭代循环之外。因此，此方法使用该#step方法仅迭代奇数，从 3 开始：

def prime5?(num)
  return true if num == 2
  return false if num <= 1 || num.even?
  3.step(Math.sqrt(num).floor, 2) { |i| return false if (num % i).zero? }
  true
end

我还认为，看看使用while循环的相同算法的“原始”实现如何执行可能会很有趣。所以，这里有一个：

def prime6?(num)
  return true if num == 2
  return false if num <= 1 || num.even?
  i = 3
  top = Math.sqrt(num).floor
  loop do
    return false if (num % i).zero?
    i += 2
    break if i >= top
  end
  true
end

基准

我对每一个都做了一个简单的基准测试，用质数 67,280,421,310,721 对每个方法的调用进行计时。例如：

start = Time.now
prime1? 67280421310721
puts "prime1? #{Time.now - start}"

start = Time.now
prime2? 67280421310721
puts "prime2? #{Time.now - start}"

# etc.

正如我怀疑我必须做的那样，我prime4?在大约 60 秒后取消了。'1'据推测，将 6.7 万亿以北的内存分配给内存，然后对结果应用正则表达式过滤器需要比 60 秒更长的时间——假设在给定的机器上首先分配必要的内存是可能的。（在我的，似乎没有：我进入irb，放入'1' * 67280421310721，制作并吃完晚餐，回到计算机，发现Killed: 9作为响应。当进程被杀死时，这看起来像是一个SignalException提升。）

其他结果是：

素数1？3.085434
素数2？1.149405
素数3？1.236517
素数5？0.748564
素数6？0.377235

一些（暂定的）结论

我认为使用 while 循环的原始解决方案最快也就不足为奇了，因为它可能比其他解决方案更接近幕后发生的事情。不过，它的速度比 快三倍Prime.prime?，这有点令人惊讶。（在查看文档中的源代码后，情况就不那么好了。对象中有很多花里胡哨的东西Prime。）

AndreiMotinga 的更新版本几乎是其原始版本的三倍，这表明该#none?方法不是很好，至少在这种情况下是这样。

最后，正则表达式版本可能很酷，但它显然没有太大的实用价值，并且在核心类的猴子补丁中使用它似乎完全可以避免。

于 2019-08-02T00:00:37.157 回答
0

所以这里的大多数答案都是以稍微不同的方式做同样的事情，这是关于 Ruby 很酷的事情之一，但我是一个相当新的学生（这就是我首先查找这个的原因）所以这里是我的版本在代码中带有注释说明：

def isprime n # starting with 2 because testing for a prime means you don't want to test division by 1
  2.upto(Math.sqrt(n)) do |x| # testing up to the square root of the number because going past there is excessive
    if n % x == 0
      # n is the number being called from the program
      # x is the number we're dividing by, counting from 2 up to the square root of the number
      return false # this means the number is not prime
    else
      return true # this means the number is prime
    end 
  end
end
于 2017-05-30T17:40:39.343 回答