Почему выполнение рубинового скрипта слишком длинное?

Question

Я пытаюсь решить проблему с http://www.beatmycode.com/challenge/5/take, и я написал сценарий:

def is_prime?(num) 
    (2...num).each do |divisor| 
    return false if num % divisor == 0 
    end 
    true 
end 
def circular_prime(num) 
    circular_primes = [] 
    if num < 2 
    return false 
    end 
    (2..num-1).each do |number| 
    is_prime?(number) 
    result = [number.to_s] 
    (0..number.to_s.size-2).each do |x| 
     var = result.last.split('') 
     result << var.unshift(var.pop).join if var.uniq.size != 1 
    end 
    circular_primes << result if result.all?{ |x| is_prime? x.to_i } 
    end 
end 

Когда я тестировал с 10, 100, 1000 и 10_000, скрипт выполняется очень быстро, но когда я тестировал с 100_000, в оболочке отображается ошибка Interrupt. Где слабый момент, и как я могу это исправить?

Answer 1

Ваш метод is_prime? слишком медленный. Некоторые незначительные улучшения могут быть:

• Вы не должны проверить divisor весь путь Шифрование до num, квадратный корень из num достаточно.
• Вы можете пропустить все четные числа, так как 2 является единственным даже простым номером .

Однако это все еще недостаточно, потому что алгоритм работает медленно. Поскольку вам нужно генерировать простые числа среди последовательных целых чисел, рассмотрите возможность использования Sieve of Eratosthenes.

---

Конечно, есть prime стандартной библиотеки, но я предполагаю, что вы хотите сделать это вручную.

Answer 2

Сложность этого сценария составляет O(n^2), поэтому ожидается, что для большого ввода потребуется много времени. Попробуйте использовать https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, чтобы найти простые числа и вспомнить, какое число является простым в некотором массиве.