如何在Ruby中测试值是否为素数？简单和困难的方式？

Question

我正在尝试创建一个程序来测试一个值是否为素数,但我不知道如何.这是我的代码:

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

每次我运行它都会返回.

NameError
uninitialized constant DetermineIfPrime::Prime

我尝试了其他方法来完成这项工作,但我认为这是我能得到的最接近的方法.

我也试过这个:

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

或者我只是做错了什么？

Answer 1

Ruby内置了一种方法来检查数字是否为素数.

require 'prime'

Prime.prime?(2)  #=> true
Prime.prime?(4)  #=> false

Answer 2

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

Answer 3

您收到的错误是因为您Prime的代码中没有要求,您需要require Prime在您的文件中执行此操作.

我在这里找到一个很酷的方法,检查数字是否为素数如下:

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

10.prime?

Answer 4

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

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

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

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