在Ruby中筛选Eratosthenes

Question

而不是从网上抓取这个算法的Ruby版本,我想根据它的描述在这里创建我自己的.但是我无法弄清楚两件事

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到两者以消除不需要的nils)

Answer 2

以下似乎有效。我取出了浮点运算并平方而不是平方根。我还用“选择”调用替换了删除循环。

while primes[index]**2 <= primes.last
      prime = primes[index]
      primes = primes.select { |x| x == prime || x%prime != 0 }
      index += 1
end

编辑：我想我知道你是如何尝试做到这一点的。以下似乎有效，并且似乎更符合您的原始方法。

while Math.sqrt(primes.last).ceil >= primes[index]
    (primes[index] * 2).step(primes.last, primes[index]) do
      |x|
      primes.delete(x)
    end
    index += 1
end