ruby 如何生成前 n 个素数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11673968/
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 do I generate the first n prime numbers?
提问by Tony Petley
I am learning Ruby and doing some math stuff. One of the things I want to do is generate prime numbers.
我正在学习 Ruby 并做一些数学运算。我想做的一件事是生成素数。
I want to generate the first ten prime numbers and the first ten only. I have no problem testing a number to see if it is a prime number or not, but was wondering what the best way is to do generate these numbers?
我想生成前十个素数和前十个。我可以测试一个数字以查看它是否是质数，但想知道生成这些数字的最佳方法是什么？
I am using the following method to determine if the number is prime:
我使用以下方法来确定数字是否为素数：
class Integer < Numeric
def is_prime?
return false if self <= 1
2.upto(Math.sqrt(self).to_i) do |x|
return false if self%x == 0
end
true
end
end
回答by Scott Olson
In Ruby 1.9 there is a Prime class you can use to generate prime numbers, or to test if a number is prime:
在 Ruby 1.9 中有一个 Prime 类可以用来生成素数，或者测试一个数是否是素数：
require 'prime'
Prime.take(10) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Prime.take_while {|p| p < 10 } #=> [2, 3, 5, 7]
Prime.prime?(19) #=> true
Prime implements the eachmethod and includes the Enumerable module, so you can do all sorts of fun stuff like filtering, mapping, and so on.
Prime 实现了该each方法并包含 Enumerable 模块，因此您可以执行各种有趣的操作，例如过滤、映射等。
回答by z5h
If you'd like to do it yourself, then something like this could work:
如果你想自己做，那么这样的事情可以工作：
class Integer < Numeric
def is_prime?
return false if self <= 1
2.upto(Math.sqrt(self).to_i) do |x|
return false if self%x == 0
end
true
end
def next_prime
n = self+1
n = n + 1 until n.is_prime?
n
end
end
Now to get the first 10 primes:
现在要获得前 10 个素数：
e = Enumerator.new do |y|
n = 2
loop do
y << n
n = n.next_prime
end
end
primes = e.take 10
回答by J?rg W Mittag
require 'prime'
Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
回答by denniss
Check out Sieve of Eratosthenes. This is not Ruby specific but it is an algorithm to generate prime numbers. The idea behind this algorithm is that you have a list/array of numbers say
查看埃拉托色尼筛。这不是特定于 Ruby 的，而是一种生成素数的算法。这个算法背后的想法是你有一个数字列表/数组说
2..1000
2..1000
You grab the first number, 2. Go through the list and eliminate everything that is divisible by 2. You will be left with everything that is not divisible by 2 other than 2 itself (e.g. [2,3,5,7,9,11...999]
您获取第一个数字 2。遍历列表并消除所有可以被 2 整除的内容。除了 2 本身之外，您将剩下所有不能被 2 整除的内容（例如 [2,3,5,7,9, 11...999]
Go to the next number, 3. And again, eliminate everything that you can divide by 3. Keep going until you reach the last number and you will get an array of prime numbers. Hope that helps.
转到下一个数字 3。再次，消除所有可以除以 3 的东西。继续前进，直到到达最后一个数字，您将得到一组素数。希望有帮助。
回答by Michael Kohl
People already mentioned the Primeclass, which definitely would be the way to go. Someone also showed you how to use an Enumeratorand I wanted to contribute a version using a Fiber(it uses your Integer#is_prime?method):
人们已经提到了Prime课程，这绝对是要走的路。有人还向您展示了如何使用Enumerator，我想贡献一个使用Fiber的版本（它使用您的Integer#is_prime?方法）：
primes = Fiber.new do
Fiber.yield 2
value = 3
loop do
Fiber.yield value if value.is_prime?
value += 2
end
end
10.times { p primes.resume }
回答by Jyothu
# First 10 Prime Numbers
number = 2
count = 1
while count < 10
j = 2
while j <= number
break if number%j == 0
j += 1
end
if j == number
puts number
count += 1
end
number += 1
end
回答by Sam S
Here is a way to generate the prime numbers up to a "max" argument from scratch, without using Prime or Math. Let me know what you think.
这是一种从头开始生成素数直到“max”参数的方法，而无需使用 Prime 或 Math。让我知道你的想法。
def prime_test max
primes = []
(1..max).each {|num|
if
(2..num-1).all? {|denom| num%denom >0}
then
primes.push(num)
end
}
puts primes
end
prime_test #enter max
回答by Shay Narang
I think this may be an expensive solution for very large max numbers but seems to work well otherwise:
我认为这对于非常大的最大数字可能是一个昂贵的解决方案，但在其他方面似乎效果很好：
def multiples array
target = array.shift
array.map{|item| item if target % item == 0}.compact
end
def prime? number
reversed_range_array = *(2..number).reverse_each
multiples_of_number = multiples(reversed_range_array)
multiples_of_number.size == 0 ? true : false
end
def primes_in_range max_number
range_array = *(2..max_number)
range_array.map{|number| number if prime?(number)}.compact
end
回答by Rishi
class Numeric
def prime?
return self == 2 if self % 2 == 0
(3..Math.sqrt(self)).step(2) do |x|
return false if self % x == 0
end
true
end
end
With this, now 3.prime?returns true, and 6.prime?returns false.
有了这个，现在3.prime?返回true，并6.prime?返回false。
Without going to the efforts to implement the sieve algorithm, time can still be saved quickly by only verifying divisibility until the square root, and skipping the odd numbers. Then, iterate through the numbers, checking for primeness.
无需努力实现筛分算法，只需验证可整除性直到平方根，跳过奇数，仍然可以快速节省时间。然后，遍历数字，检查素数。
Remember: human time > machine time.
记住：人的时间>机器的时间。
回答by Max Durden
I did this for a coding kata and used the Sieve of Eratosthenes.
我为编码卡塔做了这个，并使用了 Eratosthenes 筛。
puts "Up to which number should I look for prime numbers?"
number = $stdin.gets.chomp
n = number.to_i
array = (1..n).to_a
i = 0
while array[i]**2 < n
i = i + 1
array = array.select do |element|
element % array[i] != 0 || element / array[i] == 1
end
end
puts array.drop(1)
