Ruby

Question

我正在写一个方法 - prime_numbers - 当传递一个数字 n 时，returns n 个素数。它不应该依赖于 Ruby 的 Prime class。它应该像这样：

prime_numbers 3
=> [2, 3, 5]
prime_numbers 5
=> [2, 3, 5, 7, 11]

我第一次尝试这种方法如下：

def prime_numbers(n)
  primes = []
  i = 2

  while primes.length < n do
    divisors = (2..9).to_a.select { |x| x != i }
    primes << i if divisors.all? { |x| i % x != 0 }
    i += 1
  end
  primes
end

Edit: As pointed out, the current method is at fault by being limited to take into account divisors only up to 9. As a result, any perfect square composed of two equal primes greater than 9 is treated as a prime itself.

如果有人有意见或提示可以分享更好的方法来解决这个问题，我们将不胜感激。

Answer 1

请注意，如果数字是合数，则它的除数必须小于或等于 $\sqrt{n}$。所以你真的只需要检查 $sqrt{n}$ 就可以找到一个除数。

Answer 2

在 Ruby 1.9 中有一个素数 class 可以用来生成素数，或者测试一个数是否为素数：

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 3

对您的实施有一个好主意：

@primes = []
def prime_numbers(n)
  i = 2
  while @primes.size < n do
    @primes << i if is_prime?(i)
    i += 1
  end
  @primes
end

def is_prime?(n)
  @primes.each { |prime| return false if n % prime == 0 }
  true
end

这是基于非质数有质因数的想法:)

Ruby - 生成素数的方法

Ruby - method for generating prime numbers

math

primes