如何生成前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

- Tony Petley

---

可以采用以下方法开发更高效的算法：不要迭代偶数（仅仅跳过它们），将循环缩小到原始大小的5-10％。详细信息请参见：https://dev59.com/7oTca4cB1Zd3GeqPBfbb#32806718。 - Anatoly

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模块，因此您可以做各种有趣的事情，比如过滤、映射等等。

- Scott Olson

---

这很酷。不知道 Ruby 有一个质数类。你有没有想过如何在不使用质数类的情况下实现它？也感谢你的帮助。 - Tony Petley

不使用Prime类来实现它，我可能会使用下面回答中描述的埃拉托斯特尼筛法算法。 - Scott Olson

有没有办法获取特定范围内的质数？例如从[50, 100]？ - phuclv

@LưuVĩnhPhúc 当然可以，尝试使用 Prime.take_while {|x| x <= 100 }.drop_while {|x| x < 50 }。 - Scott Olson

@LưuVĩnhPhúc 这样做是否仍会计算出不需要的质数？ - Redoman

@LưuVĩnhPhúc 不是这样的！但我仍然需要理解原因 :) - Redoman

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

- Mark Bolusmjak

---

我在想sqrt的原因，然后在这里找到了答案：http://www.studyalgorithms.com/misc/find-the-first-n-prime-numbers-method-2/ - Alessandro De Simone

Answer 3

require 'prime'

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

- Jörg W Mittag

Answer 4

已经有人提到了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 }

- Michael Kohl

Answer 5

请查看埃拉托色尼筛法。这不是Ruby特定的，而是一种生成质数的算法。该算法背后的思想是，你有一个数字列表/数组

2..1000

你拿到了第一个数字2。遍历列表并消除所有可以被2整除的数字。最后剩下的数字中，除了2本身以外都不能被2整除（例如[2,3,5,7,9,11...999]）。

接下来拿到数字3，再次消除所有可以被3整除的数字。继续这个过程直到最后一个数字，你就会得到一个质数数组。希望这能帮到你。

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

- denniss

---

你如何“找到”“所有可被2（或3，或其他数）整除的数”？你所说的“消除”是什么意思？“达到最后一个数字”又是什么意思？如果答案不正确，将使算法失去作为* 埃拉托斯特尼筛选器 *的资格。维基百科的文章试图更加仔细地阐述它。 - Will Ness

你会发现筛法比上面的暴力方法快得多，并且在Ruby中编写并不难。 - B Seven

Answer 6

# 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

- Jyothu

---

为什么会有负分？请运行代码并查看答案。我现在再次检查了一遍。 - Jyothu

Answer 7

我为编程卡塔做了这个，并使用了埃拉托色尼筛法。

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)

- Max Durden

Answer 8

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

通过这样的方式，现在3.prime?返回true，而6.prime?返回false。

即使不去实现筛法算法，也可以通过仅验证可除性直到平方根并跳过奇数来快速节省时间。然后，迭代数字，检查质数。

记住：人类时间>机器时间。

- Rishi

---

我认为你的意思是跳过偶数。 - jmccure

抱歉，已修复，对于造成的混淆表示歉意。 - Rishi

Answer 9

这里有一种方法可以从零开始生成小于“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

- Sam S

---

很好，但根据定义（质数是大于1且除了1和本身没有其他正因子的自然数。不是质数的大于1的自然数称为合数），1不是质数，所以（2..max）将是完美的选择。 - Evgenia Karunus

最好使用primes.all?（它只检查num是否可以被质数整除-程序运行速度更快） - Evgenia Karunus

Answer 10

实现了埃拉托色尼筛法（或多或少）

def primes(size)
    arr=(0..size).to_a
    arr[0]=nil
    arr[1]=nil
    max=size
    (size/2+1).times do |n|
        if(arr[n]!=nil) then
            cnt=2*n
            while cnt <= max do
                arr[cnt]=nil
                cnt+=n
            end
        end
    end
    arr.compact!
end

此外，这是我非常喜欢的一行代码。

def primes_c a
    p=[];(2..a).each{|n| p.any?{|l|n%l==0}?nil:p.push(n)};p
end

当然，这些将在前 n 个数字中找到质数，而不是前 n 个质数，但我认为进行适应并不需要太多的努力。

- Gabber