如何生成前n个素数？

Question

我正在学习Ruby并做一些数学的东西.我想做的其中一件事是生成素数.

我想生成前十个素数和前十个素数.我测试一个数字是否有素数是没有问题的,但是想知道生成这些数字的最佳方法是什么？

我使用以下方法来确定数字是否为素数:

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

Answer 1

在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实现了该each方法并包含了Enumerable模块,因此您可以执行各种有趣的操作,如过滤,映射等.

Answer 2

如果你想自己做,那么像这样的东西可以工作:

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

现在获得前10个素数:

e = Enumerator.new do |y|
    n = 2
    loop do
        y << n
        n = n.next_prime
    end
end

primes = e.take 10

Answer 3

require 'prime'

Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Answer 4

看看Eratosthenes的Sieve.这不是特定于Ruby的,但它是一种生成素数的算法.这个算法背后的想法是你有一个列表/数组说

2..1000

你抢了先号码,2浏览清单,并消除一切由2整除你会被留下,是不是其他2比2整除本身的一切(如[2,3,5,7,9, 11 ... 999]

转到下一个数字,3.再次,消除你可以除以的所有东西.继续前进,直到你到达最后一个数字,你将得到一个素数数组.希望有所帮助.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 5

人们已经提到了这个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 }