在Ruby中筛选Eratosthenes

发布时间：2020-12-16 20:12:13 所属栏目：百科来源：网络整理

导读：而不是将这个算法的 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[ind

而不是将这个算法的 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

>为什么不迭代到数组的末尾？
>根据上面链接中的描述,循环中的数组中最后一个元素的方格大于当前的最大元素,这个循环应该被分解出来.

我确定它与修改数组长度的删除操作有关.例如,当我进入n = 10时,我的功能目前产生2,3,5,7,9,10,这显然是不正确的.有什么建议,我可以如何改变这个,使其工作,就像它应该？

解决方法

以下似乎工作.我拿出了浮点算术,而不是平方根生根.我也用“选择”调用替换了删除循环.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!