ruby - Ruby 中的 Eratosthenes 筛法

Question

我不想从网上抓取该算法的 Ruby 版本，而是想根据其描述创建自己的 here .但是我无法弄清楚两件事

def primeSieve(n)
  primes = Array.new

  for i in 0..n-2
   primes[i] = i+2
  end

  index = 0
  while Math.sqrt(primes.last).ceil > primes[index]
    (primes[index] ** 2).step(primes.length - 1, primes[index]) 
      {|x| x % primes[index] == 0 ? primes.delete(x) : ""}
    index += 1
  end

  primes
end

1. 为什么它没有迭代到数组的末尾？
2. 根据上面链接中的描述，当数组中最后一个元素的平方根大于当前素数时，循环应该被打破——我的以前做过这个。

我相当确定它与修改数组长度的删除操作有关。例如，当我输入 n=10 时，我的函数当前产生 2,3,5,7,9,10，这显然是不正确的。关于如何改变它以使其按预期工作有什么建议吗？

Answer 1

在 www.scriptol.org 有一个更快的实现:

def sieve_upto(top)
  sieve = []
  for i in 2 .. top
    sieve[i] = i
  end
  for i in 2 .. Math.sqrt(top)
    next unless sieve[i]
    (i*i).step(top, i) do |j|
      sieve[j] = nil
    end
  end
  sieve.compact
end

我认为它可以稍微改进一下:

def better_sieve_upto(n)
  s = (0..n).to_a
  s[0] = s[1] = nil
  s.each do |p|
    next unless p
    break if p * p > n
    (p*p).step(n, p) { |m| s[m] = nil }
  end
  s.compact
end

...主要是因为数组初始化更快，我认为，但它是微不足道的。 (我向两者添加了 #compact 以消除不需要的 nil)