为什么我的 ruby 脚本执行时间太长？

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 进行测试时，脚本执行速度非常快，但是当我使用 [=16= 进行测试时]，shell 显示 Interrupt 错误。弱点在哪里，我该如何解决？

Answer 1

此脚本的时间复杂度为O(n^2)，因此预计需要很长时间才能完成大量输入。尝试使用 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 查找素数并记住某个数组中哪个数字是素数。

Answer 2

您的 is_prime? 方法太慢了。一些小的改进可能是：

您不必一直测试 divisor 直到 num，即 num 够了。
您可以跳过所有偶数，因为 2 是唯一的偶数数.

然而，这仍然不够好，因为算法很慢。由于需要在连续整数之间生成素数，可以考虑使用Sieve of Eratosthenes.

当然有 prime 标准库，但我假设您想手动执行此操作。

为什么我的 ruby 脚本执行时间太长？

Why is my ruby script execution too long?

ruby

algorithm

primes

time-complexity