ruby - 在 Ruby 中提高我的 Eratosthenes 筛的效率？

Question

下面是我对 Eratosthenes 筛的实现，用于查找最高参数上限的素数。

目前，当我的参数为 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 秒。不过，我敢肯定还有很多事情可以做。