Как создать метод, который возвращает n-мерное число?

Question

Я пытаюсь написать метод, который возвращает n-е простое число.

Я разработал решение, но проблема в моем методе. Я создаю большой массив чисел, который, кажется, обрабатывается очень медленно. (1..104729).to_a, если быть точным. Я выбрал 104729, потому что max n может быть 10000, а 10000-е число - 104729. Я ищу способ оптимизации моего метода.

Это 104729 слишком большое значение? Есть ли способ написать это, чтобы я не создавал большой массив?

Вот метод:

def PrimeMover(num) 

    def is_prime(x) 
    i = 0 
    nums = (2..x).to_a 
    while nums[i] < nums.max 
     if x % nums[i] != 0 
     i += 1 
     else 
     return false 
     end 
    end 
    return true 
    end 

    primes_arr = (3..104729).to_a.select {|y| is_prime(y)} 

    primes_arr[num] 

end 

Answer 1

Вы можете использовать Руби built in #prime? method, который кажется довольно эффективным.

Код:

require 'prime' 
primes_arr = (3..104729).to_a.select &:prime? 

работает в 2-3 секунды на моей машине, которые я нахожу несколько приемлемым.

Если вам нужна еще более высокая производительность или вам действительно нужно написать свой собственный метод, попробуйте реализовать Sieve of Erathostenes. Вот некоторые Рубиновые образцы, которые: http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Ruby

Answer 2

Объединить Рубин встроенный prime library и lazy enumerator для исполнения:

require 'prime' 
(1...100_000).lazy.select(&:prime?).take(100).to_a 

Или просто, как было подчеркнуто Артуро:

Prime.take(100) 

Answer 3

require "prime" 

def find_prime(nth) 
    Prime.take(nth).last 
end 

Answer 4

Вот оптимальный осуществление пробного деления is_prime, не полагаясь на Prime класс:

Простое число - это целое число, делящееся только на 1 и само по себе, а 1 не является простым. Поэтому мы хотим знать, делится ли x на что-либо меньшее, чем х, и больше 1. Итак, мы начинаем отсчет в 2, и заканчиваем на x - 1.

def prime?(x) 
    return false if x < 2 
    2.upto(x - 1) do |n| 
    return false if (x % n).zero? 
    end 
    true 
end 

Как только x % n есть остаток, мы можем разорвать петлю и сказать, что это число не является простым. Это избавит вас от цикличности по всему диапазону. Если все возможные числа были исчерпаны, мы знаем, что число является простым.

Это еще не оптимально. Для этого вам понадобится sieve или другой алгоритм обнаружения для пробного деления. Но это большое улучшение в вашем коде. Принимая n-й до вас.