Ruby - метод для генерации простых чисел

Question

Я пишу метод - prime_numbers - то, когда передано число n, возвращается n числа простых чисел. Он не должен полагаться на класс Ruby's Prime. Он должен вести себя так:

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: Как было отмечено, в настоящее время метод виноват, будучи ограничена учитывают делители только до 9. В результате любой совершенный квадрат, состоящий из двух равных простых чисел, больших 9, рассматривается как простое.

Если у кого есть ввод или советы, они могут делиться лучшими способами подхода к этому, было бы весьма полезно.

Answer 1

Есть хорошая идея для своей реализации:

@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 

Это основывается на идее о том, что не-простые числа имеют простые множители :)

Answer 2

Обратите внимание, что если число является составным, оно должно иметь делитель, который меньше или равен $ \ sqrt {n} $. Поэтому вам действительно нужно проверить до $ sqrt {n} $, чтобы найти делитель.

Answer 3

В Ruby 1.9 есть премьер-класс, который вы можете использовать для генерации простых чисел, или, чтобы проверить, является ли число премьер:

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 реализует каждый метод и включает в себя Enumerable модуль, так что вы можете делать всевозможные забавные вещи, такие как фильтрация, картографирование и т. д.