ruby - 为什么我的 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 测试时，脚本执行得非常快，但是当我使用 100_000 进行测试时，shell 显示了一个 Interrupt 错误。弱点在哪里，我该如何解决？

Answer 1

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

• 您不必一直测试 divisor 直到 num，它的平方根num 就够了。
• 您可以跳过所有偶数，因为 2 是唯一的偶数数。

但是，这仍然不够好，因为算法很慢。由于您需要在连续整数之间生成质数，请考虑使用 Sieve of Eratosthenes .

---

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