提高红宝石中埃拉托色尼筛的效率？

Question

下面是我对埃拉托色尼筛的实现，以找到达到上限参数的质数。

目前，当我的参数为 2，000，000 时，我的代码将在大约 2 秒内完成。我看到我正在通过将数字设置为零来做一个额外的步骤，然后压缩而不是一步删除这些数字。

我将如何着手实现这一点？你还有其他提高我的代码速度的建议吗？

def sieve(upper)
  i = 0
  list = (2..upper).to_a

  (2..Math.sqrt(upper)).each do |mult|
    init = mult + i
    (init..upper-1).step(mult) do |index|
      list[index] = nil
    end
    i += 1
  end
  list.compact
end

Answer 1

你可以跳过mult不是素数的循环。

def sieve(upper)
  i = 0
  list = (2..upper).to_a
  (2..Math.sqrt(upper)).each do |mult|
    if list[i] #proceed only when mult is prime
      init = mult + i
      (init..upper-1).step(mult) do |index|
        list[index] = nil
      end
    end
    i += 1
  end
  list.compact
end

这将我的机器上的运行时间从1.9秒减少到0.7秒。不过，我相信还有很多事情可以做。