如何测试一个值是否是 Ruby 中的质数？既简单又困难？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11762043/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I test if a value is a prime number in Ruby? Both the easy and the hard way?
提问by user1542383
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?
还是我只是做错了什么？
回答by r3b00t
Ruby has built in method to check if number is prime or not.
Ruby 内置了检查数字是否为素数的方法。
require 'prime'
Prime.prime?(2) #=> true
Prime.prime?(4) #=> false
回答by AndreiMotinga
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
First, we check for 0 and 1, as they're not prime. Then we basically just check every number less than numto see if it divides. However, as explained here, for every factor greater than the square root of num, there's one that's less, so we only look between 2 and the square root.
首先，我们检查 0 和 1，因为它们不是质数。然后我们基本上只是检查每个数字 less thannum看看它是否被除。但是，正如此处所解释的，对于每个大于 的平方根的因子num，都会有一个较小的因子，因此我们只查看 2 和平方根之间的因子。
Update
更新
def is_prime?(num)
return if num <= 1
(2..Math.sqrt(num)).none? { |i| (num % i).zero? }
end
def is_prime?(num)
return if num <= 1
(2..Math.sqrt(num)).none? { |i| (num % i).zero? }
end
回答by Saurabh
The error you are getting is because you haven't required Primein your code, You need to do require Primein your file.
您收到的错误是因为您Prime的代码中没有要求，您需要require Prime在文件中执行。
One cool way I found here, to check whether a number is prime or not is following:
我在这里找到的一种很酷的方法是检查一个数字是否为素数：
class Fixnum
def prime?
('1' * self) !~ /^1?$|^(11+?)+$/
end
end
10.prime?
回答by Brian J
From an algorithmic standpoint, checking if a number is prime can be done by checking all numbers up to and including (rounding down to previous integer) said number's square root.
从算法的角度来看，检查一个数是否为素数可以通过检查所有数直到并包括（向下舍入到前一个整数）该数的平方根来完成。
For example, checking if 100 is prime involves checking everything up to 10. Checking 99 means only going to 9.
例如，检查 100 是否为质数涉及检查直到 10 的所有内容。检查 99 意味着只去 9。
** Another way to think about it **
Each factor has a pair (3 is a factor of 36, and 3's pair is 12).
The pair is on the other side of the square root (square root of 6 is 36, 3 < 6, 12 > 6).
So by checking everything until the square root (and not going over) ensures you check all possible factors.
**另一种思考方式**
每个因子都有一对（3是36的因子，3的对是12）。
该对位于平方根的另一侧（6 的平方根为 36, 3 < 6, 12 > 6）。
因此，通过检查所有内容直到平方根（而不是超过）确保您检查所有可能的因素。
You can make it quicker by having a list of prime numbers to compare, as you are doing. If you have a maximum limit that's reasonably small, you could just have a list of primes and do a direct lookup to see if that number is prime.
您可以通过列出要比较的素数列表来加快速度，就像您正在做的那样。如果您有一个相当小的最大限制，您可以只拥有一个质数列表并直接查找该数字是否为质数。
回答by Brent
def is_prime?(num)
Math.sqrt(num).floor.downto(2).each {|i| return false if num % i == 0}
true
end
lol sorry for resurrecting a super old questions, but it's the first one that came up in google.
很抱歉复活了一个超级老问题，但这是第一个出现在谷歌的问题。
Basically, it loops through possible divisors, using the square root as the max number to check to save time on very large numbers.
基本上，它遍历可能的除数，使用平方根作为最大数来检查以节省非常大的数的时间。
回答by Lorena Nicole
In response to your question, while you can approach the problem by using Ruby's Prime I am going to write code to answer it on its own.
针对您的问题，虽然您可以使用 Ruby 的 Prime 来解决问题，但我将编写代码来自行回答。
Consider that all you need to do is determine a factor that is smaller than the integer's square root. Any number larger than the integer's square root as a factor requires a second factor to render the number as the product. (e.g. square root of 15 is approx 3.8 so if you find 5 as a factor it is only a factor with the factor pair 3 and 5!!)
考虑到您需要做的就是确定一个小于整数平方根的因子。任何大于整数平方根的数作为因数都需要第二个因数才能将该数呈现为乘积。（例如，15 的平方根大约是 3.8，所以如果你发现 5 作为一个因子，它只是一个因子对 3 和 5 的因子！！）
def isPrime?(num)
(2..Math.sqrt(num)).each { |i| return false if num % i == 0}
true
end
Hope that helps!!
希望有帮助！！
回答by reppard
If you are going to use any Prime functions you must include the Prime library. This problem can be solved without the use of the prime library however.
如果要使用任何 Prime 函数，则必须包含 Prime 库。然而，这个问题可以在不使用素数库的情况下解决。
def isPrime?(num)
(2..Math.sqrt(num)).each { |i|
if num % i == 0 && i < num
return false
end
}
true
end
Something like this would work.
像这样的事情会起作用。
回答by sunny
Try this
尝试这个
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
回答by Dalthariel
So most of the answers here are doing the same thing in slightly different ways which is one of the cool things about Ruby, but I'm a pretty new student (which is why I was looking this up in the first place) and so here's my version with comment explanations in the code:
所以这里的大多数答案都以稍微不同的方式做同样的事情，这是关于 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
回答by BobRodes
(To first answer the question: yes, you are doing something wrong. As BLUEPIXY mentions, you need to put require 'prime'somewhere above the line that calls Prime.prime?. Typically on line 1.)
（首先回答这个问题：是的，你做错了什么。正如 BLUEPIXY 提到的，你需要把require 'prime'某个地方放在调用 的行上方Prime.prime?。通常在第 1 行。）
Now, a lot of answers have been given that don't use Prime.prime?, and I thought it might be interesting to benchmark some of them, along with a possible improvement of my own that I had in mind.
现在，已经给出了很多不使用的答案Prime.prime?，我认为对其中一些进行基准测试可能会很有趣，以及我自己想到的可能的改进。
TL;DR
TL; 博士
I benchmarked several solutions, including a couple of my own; using a whileloop and skipping even numbers performs best.
我对几个解决方案进行了基准测试，包括我自己的几个；使用while循环并跳过偶数效果最好。
Methods tested
测试方法
Here are the methods I used from the answers:
以下是我从答案中使用的方法：
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+?)+$/
end
prime1?is AndreiMotinga's updated version. prime2?is his original version (with the superfluous eachmethod removed). prime3?is Reboot's, using primelibrary. prime4?is Saurabh's regex version (minus the Fixnummonkey-patch).
prime1?是 AndreiMotinga 的更新版本。prime2?是他的原始版本（each删除了多余的方法）。prime3?是重新启动的，使用prime库。prime4?是 Saurabh 的正则表达式版本（减去Fixnum猴子补丁）。
A couple more methods to test
几种测试方法
The improvement I had in mind was to leverage the fact that even numbers can't be prime, and leave them out of the iteration loop. So, this method uses the #stepmethod to iterate over only odd numbers, starting with 3:
我想到的改进是利用偶数不能是质数的事实，并将它们排除在迭代循环之外。因此，此方法使用#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
I thought as well that it might be interesting to see how a "primitive" implementation of the same algorithm, using a whileloop, might perform. So, here's one:
我还认为，看看使用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
Benchmarks
基准
I did a simple benchmark on each of these, timing a call to each method with the prime number 67,280,421,310,721. For example:
我对其中的每一个都做了一个简单的基准测试，用质数 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.
As I suspected I would have to do, I canceled prime4?after about 60 seconds. Presumably, it takes quite a bit longer than 60 seconds to assign north of 6.7 trillion '1''s to memory, and then apply a regex filter to the result — assuming it's possible on a given machine to allocate the necessary memory in the first place. (On mine, it would seem that there isn't: I went into irb, put in '1' * 67280421310721, made and ate dinner, came back to the computer, and found Killed: 9as the response. That looks like a SignalExceptionraised when the process got killed.)
正如我怀疑我必须做的那样，我prime4?在大约 60 秒后取消了。据推测，将 6.7 万亿以北的'1'内存分配给内存，然后对结果应用正则表达式过滤器所需的时间比 60 秒要长得多——假设有可能在给定的机器上首先分配必要的内存。（在我看来，似乎没有：我进入irb，放入'1' * 67280421310721，制作并吃晚饭，回到计算机，发现Killed: 9作为响应。SignalException当进程被终止时，这看起来像一个凸起。）
The other results are:
其他结果是：
prime1? 3.085434
prime2? 1.149405
prime3? 1.236517
prime5? 0.748564
prime6? 0.377235
素数1？3.085434
素数2？1.149405
素数3？1.236517
prime5？0.748564
素数6？0.377235
Some (tentative) conclusions
一些（暂定的）结论
I suppose that isn't really surprising that the primitive solution with the while loop is fastest, since it's probably closer than the others to what's going on under the hood. It isa bit surprising that it's three times faster than Prime.prime?, though. (After looking at the source code in the doc it is less so. There are lots of bells and whistles in the Primeobject.)
我认为使用 while 循环的原始解决方案最快并不令人惊讶，因为它可能比其他解决方案更接近引擎盖下发生的事情。这是一个有点出人意料，它比快三倍Prime.prime?，虽然。（查看文档中的源代码后，情况就不那么明显了。对象中有很多花里胡哨的东西Prime。）
AndreiMotinga's updated version is nearly three times as slow as his original, which suggests that the #none?method isn't much of a performer, at least in this context.
AndreiMotinga 的更新版本几乎是原始版本的三倍，这表明该#none?方法不是很有效，至少在这种情况下是这样。
Finally, the regex version might be cool, but it certainly doesn't appear to have much practical value, and using it in a monkey-patch of a core class looks like something to avoid entirely.
最后，正则表达式版本可能很酷，但它似乎没有太大的实用价值，并且在核心类的猴子补丁中使用它看起来像是完全避免的事情。
